|
111
|
1 /* A scheduling optimizer for Graphite
|
|
131
|
2 Copyright (C) 2012-2018 Free Software Foundation, Inc.
|
|
111
|
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 {
|
|
131
|
163 dump_user_location_t loc = find_loop_location
|
|
111
|
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 {
|
|
131
|
185 dump_user_location_t loc = find_loop_location
|
|
111
|
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 */
|
