gcc/graphite-optimize-isl.c

   1 /* A scheduling optimizer for Graphite
   2    Copyright (C) 2012-2017 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 #include "graphite.h"
  41
  42
  43 /* get_schedule_for_node_st - Improve schedule for the schedule node.
  44    Only Simple loop tiling is considered.  */
  45
  46 static __isl_give isl_schedule_node *
  47 get_schedule_for_node_st (__isl_take isl_schedule_node *node, void *user)
  48 {
  49   if (user)
  50     return node;
  51
  52   if (isl_schedule_node_get_type (node) != isl_schedule_node_band
  53       || isl_schedule_node_n_children (node) != 1)
  54     return node;
  55
  56   isl_space *space = isl_schedule_node_band_get_space (node);
  57   unsigned dims = isl_space_dim (space, isl_dim_set);
  58   isl_schedule_node *child = isl_schedule_node_get_child (node, 0);
  59   isl_schedule_node_type type = isl_schedule_node_get_type (child);
  60   isl_space_free (space);
  61   isl_schedule_node_free (child);
  62
  63   if (type != isl_schedule_node_leaf)
  64     return node;
  65
  66   if (dims <= 1 || !isl_schedule_node_band_get_permutable (node))
  67     {
  68       if (dump_file && dump_flags)
  69         fprintf (dump_file, "not tiled\n");
  70       return node;
  71     }
  72
  73   /* Tile loops.  */
  74   space = isl_schedule_node_band_get_space (node);
  75   isl_multi_val *sizes = isl_multi_val_zero (space);
  76   long tile_size = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
  77   isl_ctx *ctx = isl_schedule_node_get_ctx (node);
  78
  79   for (unsigned i = 0; i < dims; i++)
  80     {
  81       sizes = isl_multi_val_set_val (sizes, i,
  82                                      isl_val_int_from_si (ctx, tile_size));
  83       if (dump_file && dump_flags)
  84         fprintf (dump_file, "tiled by %ld\n", tile_size);
  85     }
  86
  87   node = isl_schedule_node_band_tile (node, sizes);
  88   node = isl_schedule_node_child (node, 0);
  89
  90   return node;
  91 }
  92
  93 static isl_union_set *
  94 scop_get_domains (scop_p scop)
  95 {
  96   int i;
  97   poly_bb_p pbb;
  98   isl_space *space = isl_set_get_space (scop->param_context);
  99   isl_union_set *res = isl_union_set_empty (space);
 100
 101   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 102     res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));
 103
 104   return res;
 105 }
 106
 107 /* Compute the schedule for SCOP based on its parameters, domain and set of
 108    constraints.  Then apply the schedule to SCOP.  */
 109
 110 static bool
 111 optimize_isl (scop_p scop)
 112 {
 113   int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
 114   int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS);
 115   if (max_operations)
 116     isl_ctx_set_max_operations (scop->isl_context, max_operations);
 117   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
 118
 119   isl_union_set *domain = scop_get_domains (scop);
 120
 121   /* Simplify the dependences on the domain.  */
 122   scop_get_dependences (scop);
 123   isl_union_map *dependences
 124     = isl_union_map_gist_domain (isl_union_map_copy (scop->dependence),
 125                                  isl_union_set_copy (domain));
 126   isl_union_map *validity
 127     = isl_union_map_gist_range (dependences, isl_union_set_copy (domain));
 128
 129   /* FIXME: proximity should not be validity.  */
 130   isl_union_map *proximity = isl_union_map_copy (validity);
 131
 132   isl_schedule_constraints *sc = isl_schedule_constraints_on_domain (domain);
 133   sc = isl_schedule_constraints_set_proximity (sc, proximity);
 134   sc = isl_schedule_constraints_set_validity (sc, isl_union_map_copy (validity));
 135   sc = isl_schedule_constraints_set_coincidence (sc, validity);
 136
 137   isl_options_set_schedule_serialize_sccs (scop->isl_context, 0);
 138   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
 139   isl_options_set_schedule_max_constant_term (scop->isl_context, 20);
 140   isl_options_set_schedule_max_coefficient (scop->isl_context, 20);
 141   isl_options_set_tile_scale_tile_loops (scop->isl_context, 0);
 142   /* Generate loop upper bounds that consist of the current loop iterator, an
 143      operator (< or <=) and an expression not involving the iterator.  If this
 144      option is not set, then the current loop iterator may appear several times
 145      in the upper bound.  See the isl manual for more details.  */
 146   isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1);
 147
 148   scop->transformed_schedule = isl_schedule_constraints_compute_schedule (sc);
 149   scop->transformed_schedule =
 150     isl_schedule_map_schedule_node_bottom_up (scop->transformed_schedule,
 151                                               get_schedule_for_node_st, NULL);
 152   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT);
 153
 154   isl_ctx_reset_operations (scop->isl_context);
 155   isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
 156   if (!scop->transformed_schedule
 157       || isl_ctx_last_error (scop->isl_context) == isl_error_quota)
 158     {
 159       if (dump_file && dump_flags)
 160         fprintf (dump_file, "isl timed out --param max-isl-operations=%d\n",
 161                  max_operations);
 162       return false;
 163     }
 164
 165   gcc_assert (scop->original_schedule);
 166   isl_union_map *original = isl_schedule_get_map (scop->original_schedule);
 167   isl_union_map *transformed = isl_schedule_get_map (scop->transformed_schedule);
 168   bool same_schedule = isl_union_map_is_equal (original, transformed);
 169   isl_union_map_free (original);
 170   isl_union_map_free (transformed);
 171
 172   if (same_schedule)
 173     {
 174       if (dump_file)
 175         {
 176           fprintf (dump_file, "[scheduler] isl optimized schedule is "
 177                    "identical to the original schedule.\n");
 178           print_schedule_ast (dump_file, scop->original_schedule, scop);
 179         }
 180       isl_schedule_free (scop->transformed_schedule);
 181       scop->transformed_schedule = isl_schedule_copy (scop->original_schedule);
 182       return false;
 183     }
 184
 185   return true;
 186 }
 187
 188 /* Apply graphite transformations to all the basic blocks of SCOP.  */
 189
 190 bool
 191 apply_poly_transforms (scop_p scop)
 192 {
 193   if (flag_loop_nest_optimize)
 194     return optimize_isl (scop);
 195
 196   if (!flag_graphite_identity && !flag_loop_parallelize_all)
 197     return false;
 198
 199   /* Generate code even if we did not apply any real transformation.
 200      This also allows to check the performance for the identity
 201      transformation: GIMPLE -> GRAPHITE -> GIMPLE.  */
 202   gcc_assert (scop->original_schedule);
 203   scop->transformed_schedule = isl_schedule_copy (scop->original_schedule);
 204   return true;
 205 }
 206
 207 #endif /* HAVE_isl */