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