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 *
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 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
apply_poly_transforms(scop_p scop)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