1 /* A scheduling optimizer for Graphite
2 Copyright (C) 2012-2019 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 *
get_schedule_for_node_st(__isl_take isl_schedule_node * node,void * user)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 *
scop_get_domains(scop_p scop)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
optimize_isl(scop_p scop)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
apply_poly_transforms(scop_p scop)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 */
226