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