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 */ 208