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 #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
  41 #include <isl/constraint.h>
  42 #include <isl/set.h>
  43 #include <isl/union_set.h>
  44 #include <isl/map.h>
  45 #include <isl/union_map.h>
  46 #include <isl/schedule.h>
  47 #include <isl/band.h>
  48 #include <isl/aff.h>
  49 #include <isl/options.h>
  50 #include <isl/ctx.h>
  51 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  52 #include <isl/schedule_node.h>
  53 #endif
  54
  55 #include "graphite-poly.h"
  56
  57 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  58
  59 /* get_schedule_for_node_st - Improve schedule for the schedule node.
  60    Only Simple loop tiling is considered.  */
  61
  62 static __isl_give isl_schedule_node *
  63 get_schedule_for_node_st (__isl_take isl_schedule_node *node, void *user)
  64 {
  65   if (user)
  66     return node;
  67
  68   if (isl_schedule_node_get_type (node) != isl_schedule_node_band
  69       || isl_schedule_node_n_children (node) != 1)
  70     return node;
  71
  72   isl_space *space = isl_schedule_node_band_get_space (node);
  73   unsigned dims = isl_space_dim (space, isl_dim_set);
  74   isl_schedule_node *child = isl_schedule_node_get_child (node, 0);
  75   isl_schedule_node_type type = isl_schedule_node_get_type (child);
  76   isl_space_free (space);
  77   isl_schedule_node_free (child);
  78
  79   if (type != isl_schedule_node_leaf)
  80     return node;
  81
  82   if (dims <= 1 || !isl_schedule_node_band_get_permutable (node))
  83     {
  84       if (dump_file && dump_flags)
  85         fprintf (dump_file, "not tiled\n");
  86       return node;
  87     }
  88
  89   /* Tile loops.  */
  90   space = isl_schedule_node_band_get_space (node);
  91   isl_multi_val *sizes = isl_multi_val_zero (space);
  92   long tile_size = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
  93   isl_ctx *ctx = isl_schedule_node_get_ctx (node);
  94
  95   for (unsigned i = 0; i < dims; i++)
  96     {
  97       sizes = isl_multi_val_set_val (sizes, i,
  98                                      isl_val_int_from_si (ctx, tile_size));
  99       if (dump_file && dump_flags)
 100         fprintf (dump_file, "tiled by %ld\n", tile_size);
 101     }
 102
 103   node = isl_schedule_node_band_tile (node, sizes);
 104   node = isl_schedule_node_child (node, 0);
 105
 106   return node;
 107 }
 108
 109 /* get_schedule_map_st - Improve the schedule by performing other loop
 110    optimizations. _st ending is for schedule tree version of this
 111    function (see get_schedule_map below for the band forest version).
 112
 113    Do a depth-first post-order traversal of the nodes in a schedule
 114    tree and apply get_schedule_for_node_st on them to improve the schedule.
 115   */
 116
 117 static __isl_give isl_union_map *
 118 get_schedule_map_st (__isl_keep isl_schedule *schedule)
 119 {
 120
 121   schedule = isl_schedule_map_schedule_node_bottom_up (schedule,
 122                                                        get_schedule_for_node_st,
 123                                                        NULL);
 124   isl_union_map *schedule_map = isl_schedule_get_map (schedule);
 125   return schedule_map;
 126 }
 127 #else
 128
 129 /* get_tile_map - Create a map that describes a n-dimensonal tiling.
 130
 131    get_tile_map creates a map from a n-dimensional scattering space into an
 132    2*n-dimensional scattering space. The map describes a rectangular tiling.
 133
 134    Example:
 135      SCHEDULE_DIMENSIONS = 2, PARAMETER_DIMENSIONS = 1, TILE_SIZE = 32
 136
 137     tile_map := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
 138                          t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
 139                          t1 % 32 = 0 and t1 <= s1 < t1 + 32}
 140
 141    Before tiling:
 142
 143    for (i = 0; i < N; i++)
 144      for (j = 0; j < M; j++)
 145         S(i,j)
 146
 147    After tiling:
 148
 149    for (t_i = 0; t_i < N; i+=32)
 150      for (t_j = 0; t_j < M; j+=32)
 151         for (i = t_i; i < min(t_i + 32, N); i++)  | Unknown that N % 32 = 0
 152           for (j = t_j; j < t_j + 32; j++)        |   Known that M % 32 = 0
 153             S(i,j)
 154   */
 155
 156 static isl_basic_map *
 157 get_tile_map (isl_ctx *ctx, int schedule_dimensions, int tile_size)
 158 {
 159   /* We construct
 160
 161      tile_map := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
 162                         s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
 163                         s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}
 164
 165      and project out the auxilary dimensions a0 and a1.  */
 166   isl_space *space
 167     = isl_space_alloc (ctx, 0, schedule_dimensions, schedule_dimensions * 3);
 168   isl_basic_map *tile_map = isl_basic_map_universe (isl_space_copy (space));
 169
 170   isl_local_space *local_space = isl_local_space_from_space (space);
 171
 172   for (int x = 0; x < schedule_dimensions; x++)
 173     {
 174       int sX = x;
 175       int tX = x;
 176       int pX = schedule_dimensions + x;
 177       int aX = 2 * schedule_dimensions + x;
 178
 179       isl_constraint *c;
 180
 181       /* sX = aX * tile_size; */
 182       c = isl_equality_alloc (isl_local_space_copy (local_space));
 183       isl_constraint_set_coefficient_si (c, isl_dim_out, sX, 1);
 184       isl_constraint_set_coefficient_si (c, isl_dim_out, aX, -tile_size);
 185       tile_map = isl_basic_map_add_constraint (tile_map, c);
 186
 187       /* pX = sX; */
 188       c = isl_equality_alloc (isl_local_space_copy (local_space));
 189       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
 190       isl_constraint_set_coefficient_si (c, isl_dim_in, sX, -1);
 191       tile_map = isl_basic_map_add_constraint (tile_map, c);
 192
 193       /* tX <= pX */
 194       c = isl_inequality_alloc (isl_local_space_copy (local_space));
 195       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
 196       isl_constraint_set_coefficient_si (c, isl_dim_out, tX, -1);
 197       tile_map = isl_basic_map_add_constraint (tile_map, c);
 198
 199       /* pX <= tX + (tile_size - 1) */
 200       c = isl_inequality_alloc (isl_local_space_copy (local_space));
 201       isl_constraint_set_coefficient_si (c, isl_dim_out, tX, 1);
 202       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, -1);
 203       isl_constraint_set_constant_si (c, tile_size - 1);
 204       tile_map = isl_basic_map_add_constraint (tile_map, c);
 205     }
 206
 207   /* Project out auxiliary dimensions.
 208
 209      The auxiliary dimensions are transformed into existentially quantified
 210      ones.
 211      This reduces the number of visible scattering dimensions and allows isl
 212      to produces better code.  */
 213   tile_map =
 214       isl_basic_map_project_out (tile_map, isl_dim_out,
 215                                  2 * schedule_dimensions, schedule_dimensions);
 216   isl_local_space_free (local_space);
 217   return tile_map;
 218 }
 219
 220 /* get_schedule_for_band - Get the schedule for this BAND.
 221
 222    Polly applies transformations like tiling on top of the isl calculated
 223    value.
 224    This can influence the number of scheduling dimension. The number of
 225    schedule dimensions is returned in DIMENSIONS.  */
 226
 227 static isl_union_map *
 228 get_schedule_for_band (isl_band *band, int *dimensions)
 229 {
 230   isl_union_map *partial_schedule;
 231   isl_ctx *ctx;
 232   isl_space *space;
 233   isl_basic_map *tile_map;
 234   isl_union_map *tile_umap;
 235
 236   partial_schedule = isl_band_get_partial_schedule (band);
 237   *dimensions = isl_band_n_member (band);
 238
 239   /* It does not make any sense to tile a band with just one dimension.  */
 240   if (*dimensions == 1)
 241     {
 242       if (dump_file && dump_flags)
 243         fprintf (dump_file, "not tiled\n");
 244       return partial_schedule;
 245     }
 246
 247   if (dump_file && dump_flags)
 248     fprintf (dump_file, "tiled by %d\n",
 249              PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 250
 251   ctx = isl_union_map_get_ctx (partial_schedule);
 252   space = isl_union_map_get_space (partial_schedule);
 253
 254   tile_map = get_tile_map (ctx, *dimensions,
 255                            PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 256   tile_umap = isl_union_map_from_map (isl_map_from_basic_map (tile_map));
 257   tile_umap = isl_union_map_align_params (tile_umap, space);
 258   *dimensions = 2 * *dimensions;
 259
 260   return isl_union_map_apply_range (partial_schedule, tile_umap);
 261 }
 262
 263
 264 /* get_schedule_for_band_list - Get the scheduling map for a list of bands.
 265
 266    We walk recursively the forest of bands to combine the schedules of the
 267    individual bands to the overall schedule.  In case tiling is requested,
 268    the individual bands are tiled.  */
 269
 270 static isl_union_map *
 271 get_schedule_for_band_list (isl_band_list *band_list)
 272 {
 273   int num_bands, i;
 274   isl_union_map *schedule;
 275   isl_ctx *ctx;
 276
 277   ctx = isl_band_list_get_ctx (band_list);
 278   num_bands = isl_band_list_n_band (band_list);
 279   schedule = isl_union_map_empty (isl_space_params_alloc (ctx, 0));
 280
 281   for (i = 0; i < num_bands; i++)
 282     {
 283       isl_band *band;
 284       isl_union_map *partial_schedule;
 285       int schedule_dimensions;
 286       isl_space *space;
 287
 288       band = isl_band_list_get_band (band_list, i);
 289       partial_schedule = get_schedule_for_band (band, &schedule_dimensions);
 290       space = isl_union_map_get_space (partial_schedule);
 291
 292       if (isl_band_has_children (band))
 293         {
 294           isl_band_list *children = isl_band_get_children (band);
 295           isl_union_map *suffixSchedule
 296             = get_schedule_for_band_list (children);
 297           partial_schedule
 298             = isl_union_map_flat_range_product (partial_schedule,
 299                                                 suffixSchedule);
 300           isl_band_list_free (children);
 301         }
 302
 303       schedule = isl_union_map_union (schedule, partial_schedule);
 304
 305       isl_band_free (band);
 306       isl_space_free (space);
 307     }
 308
 309   return schedule;
 310 }
 311
 312 static isl_union_map *
 313 get_schedule_map (isl_schedule *schedule)
 314 {
 315   isl_band_list *bandList = isl_schedule_get_band_forest (schedule);
 316   isl_union_map *schedule_map = get_schedule_for_band_list (bandList);
 317   isl_band_list_free (bandList);
 318   return schedule_map;
 319 }
 320 #endif
 321
 322 static isl_stat
 323 get_single_map (__isl_take isl_map *map, void *user)
 324 {
 325   isl_map **single_map = (isl_map **)user;
 326   *single_map = map;
 327   return isl_stat_ok;
 328 }
 329
 330 static void
 331 apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
 332 {
 333   int i;
 334   poly_bb_p pbb;
 335
 336   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 337     {
 338       isl_set *domain = isl_set_copy (pbb->domain);
 339       isl_map *stmt_schedule;
 340
 341       isl_union_map *stmt_band
 342         = isl_union_map_intersect_domain (isl_union_map_copy (schedule_map),
 343                                           isl_union_set_from_set (domain));
 344       isl_union_map_foreach_map (stmt_band, get_single_map, &stmt_schedule);
 345       isl_map_free (pbb->transformed);
 346       pbb->transformed = stmt_schedule;
 347       isl_union_map_free (stmt_band);
 348     }
 349 }
 350
 351 static isl_union_set *
 352 scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
 353 {
 354   int i;
 355   poly_bb_p pbb;
 356   isl_space *space = isl_set_get_space (scop->param_context);
 357   isl_union_set *res = isl_union_set_empty (space);
 358
 359   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 360     res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));
 361
 362     return res;
 363 }
 364
 365 static const int CONSTANT_BOUND = 20;
 366
 367 /* Compute the schedule for SCOP based on its parameters, domain and set of
 368    constraints.  Then apply the schedule to SCOP.  */
 369
 370 bool
 371 optimize_isl (scop_p scop)
 372 {
 373 #ifdef HAVE_ISL_CTX_MAX_OPERATIONS
 374   int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
 375   int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS);
 376   if (max_operations)
 377     isl_ctx_set_max_operations (scop->isl_context, max_operations);
 378 #endif
 379   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
 380
 381   isl_union_set *domain = scop_get_domains (scop);
 382   isl_union_map *dependences = scop_get_dependences (scop);
 383   dependences
 384     = isl_union_map_gist_domain (dependences, isl_union_set_copy (domain));
 385   dependences
 386     = isl_union_map_gist_range (dependences, isl_union_set_copy (domain));
 387   isl_union_map *validity = dependences;
 388   isl_union_map *proximity = isl_union_map_copy (validity);
 389
 390 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 391   isl_schedule_constraints *schedule_constraints;
 392   schedule_constraints = isl_schedule_constraints_on_domain (domain);
 393   schedule_constraints
 394     = isl_schedule_constraints_set_proximity (schedule_constraints,
 395                                               proximity);
 396   schedule_constraints
 397     = isl_schedule_constraints_set_validity (schedule_constraints,
 398                                              isl_union_map_copy (validity));
 399   schedule_constraints
 400     = isl_schedule_constraints_set_coincidence (schedule_constraints,
 401                                                 validity);
 402 #endif
 403
 404   isl_options_set_schedule_max_constant_term (scop->isl_context, CONSTANT_BOUND);
 405   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
 406 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 407   /* ISL-0.15 or later.  */
 408   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
 409 #else
 410   isl_options_set_schedule_fuse (scop->isl_context, ISL_SCHEDULE_FUSE_MIN);
 411 #endif
 412
 413 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 414   isl_schedule *schedule
 415     = isl_schedule_constraints_compute_schedule (schedule_constraints);
 416 #else
 417   isl_schedule *schedule
 418     = isl_union_set_compute_schedule (domain, validity, proximity);
 419 #endif
 420
 421   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT);
 422
 423 #ifdef HAVE_ISL_CTX_MAX_OPERATIONS
 424   isl_ctx_reset_operations (scop->isl_context);
 425   isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
 426   if (!schedule || isl_ctx_last_error (scop->isl_context) == isl_error_quota)
 427     {
 428       if (dump_file && dump_flags)
 429         fprintf (dump_file, "ISL timed out at %d operations\n",
 430                  max_operations);
 431       if (schedule)
 432         isl_schedule_free (schedule);
 433       return false;
 434     }
 435 #else
 436   if (!schedule)
 437     return false;
 438 #endif
 439
 440 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 441   isl_union_map *schedule_map = get_schedule_map_st (schedule);
 442 #else
 443   isl_union_map *schedule_map = get_schedule_map (schedule);
 444 #endif
 445
 446   if (isl_union_map_is_equal (scop->original_schedule, schedule_map))
 447     {
 448       if (dump_file && dump_flags)
 449         fprintf (dump_file, "\nISL schedule same as original schedule\n");
 450
 451       isl_schedule_free (schedule);
 452       isl_union_map_free (schedule_map);
 453       return false;
 454     }
 455   else
 456     {
 457       apply_schedule_map_to_scop (scop, schedule_map);
 458       isl_schedule_free (schedule);
 459       isl_union_map_free (schedule_map);
 460       return true;
 461     }
 462 }
 463
 464 #endif /* HAVE_isl */