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 location_t loc = find_loop_location 164 (scop->scop_info->region.entry->dest->loop_father); 165 if (isl_ctx_last_error (scop->isl_context) == isl_error_quota) 166 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, 167 "loop nest not optimized, optimization timed out " 168 "after %d operations [--param max-isl-operations]\n", 169 max_operations); 170 else 171 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, 172 "loop nest not optimized, ISL signalled an error\n"); 173 return false; 174 } 175 176 gcc_assert (scop->original_schedule); 177 isl_union_map *original = isl_schedule_get_map (scop->original_schedule); 178 isl_union_map *transformed = isl_schedule_get_map (scop->transformed_schedule); 179 bool same_schedule = isl_union_map_is_equal (original, transformed); 180 isl_union_map_free (original); 181 isl_union_map_free (transformed); 182 183 if (same_schedule) 184 { 185 location_t loc = find_loop_location 186 (scop->scop_info->region.entry->dest->loop_father); 187 dump_printf_loc (MSG_NOTE, loc, 188 "loop nest not optimized, optimized schedule is " 189 "identical to original schedule\n"); 190 if (dump_file) 191 print_schedule_ast (dump_file, scop->original_schedule, scop); 192 isl_schedule_free (scop->transformed_schedule); 193 scop->transformed_schedule = isl_schedule_copy (scop->original_schedule); 194 return flag_graphite_identity || flag_loop_parallelize_all; 195 } 196 197 return true; 198 } 199 200 /* Apply graphite transformations to all the basic blocks of SCOP. */ 201 202 bool 203 apply_poly_transforms (scop_p scop) 204 { 205 if (flag_loop_nest_optimize) 206 return optimize_isl (scop); 207 208 if (!flag_graphite_identity && !flag_loop_parallelize_all) 209 return false; 210 211 /* Generate code even if we did not apply any real transformation. 212 This also allows to check the performance for the identity 213 transformation: GIMPLE -> GRAPHITE -> GIMPLE. */ 214 gcc_assert (scop->original_schedule); 215 scop->transformed_schedule = isl_schedule_copy (scop->original_schedule); 216 return true; 217 } 218 219 #endif /* HAVE_isl */ 220