gcc/graphite-optimize-isl.c

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