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