]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Data dependence analysis for Graphite. |
8d9254fc | 2 | Copyright (C) 2009-2020 Free Software Foundation, Inc. |
2abae5f1 SP |
3 | Contributed by Sebastian Pop <sebastian.pop@amd.com> and |
4 | Konrad Trifunovic <konrad.trifunovic@inria.fr>. | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
4d776011 DE |
22 | #define USES_ISL |
23 | ||
2abae5f1 | 24 | #include "config.h" |
33ad93b9 | 25 | |
eae1a5d4 | 26 | #ifdef HAVE_isl |
33ad93b9 | 27 | |
2abae5f1 SP |
28 | #include "system.h" |
29 | #include "coretypes.h" | |
c7131fb2 | 30 | #include "backend.h" |
9fdcd34e | 31 | #include "cfghooks.h" |
40e23961 | 32 | #include "tree.h" |
c7131fb2 | 33 | #include "gimple.h" |
c7131fb2 | 34 | #include "fold-const.h" |
5be5c238 | 35 | #include "gimple-iterator.h" |
442b4905 | 36 | #include "tree-ssa-loop.h" |
7a1c57d3 | 37 | #include "tree-pass.h" |
2abae5f1 | 38 | #include "cfgloop.h" |
2abae5f1 | 39 | #include "tree-data-ref.h" |
cf98f0f4 | 40 | #include "graphite.h" |
e37f165f | 41 | |
33ad93b9 | 42 | /* Add the constraints from the set S to the domain of MAP. */ |
2abae5f1 | 43 | |
33ad93b9 RG |
44 | static isl_map * |
45 | constrain_domain (isl_map *map, isl_set *s) | |
e37f165f | 46 | { |
33ad93b9 RG |
47 | isl_space *d = isl_map_get_space (map); |
48 | isl_id *id = isl_space_get_tuple_id (d, isl_dim_in); | |
b5eb099f | 49 | |
33ad93b9 RG |
50 | s = isl_set_set_tuple_id (s, id); |
51 | isl_space_free (d); | |
14b1747c | 52 | return isl_map_coalesce (isl_map_intersect_domain (map, s)); |
b5eb099f SP |
53 | } |
54 | ||
24757752 | 55 | /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain. */ |
b5eb099f | 56 | |
33ad93b9 RG |
57 | static isl_map * |
58 | add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb) | |
b5eb099f | 59 | { |
33ad93b9 | 60 | isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses), |
24757752 | 61 | isl_set_copy (pdr->subscript_sizes)); |
14b1747c AK |
62 | x = isl_map_coalesce (x); |
63 | return constrain_domain (x, isl_set_copy (pbb->domain)); | |
b5eb099f SP |
64 | } |
65 | ||
312ce401 SP |
66 | /* Returns an isl description of all memory operations in SCOP. The memory |
67 | reads are returned in READS and writes in MUST_WRITES and MAY_WRITES. */ | |
b5eb099f | 68 | |
312ce401 | 69 | static void |
f371d337 RB |
70 | scop_get_reads_and_writes (scop_p scop, isl_union_map *&reads, |
71 | isl_union_map *&must_writes, | |
72 | isl_union_map *&may_writes) | |
b5eb099f | 73 | { |
33ad93b9 RG |
74 | int i, j; |
75 | poly_bb_p pbb; | |
76 | poly_dr_p pdr; | |
b5eb099f | 77 | |
adba512d | 78 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
e37f165f | 79 | { |
312ce401 | 80 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) { |
33ad93b9 | 81 | if (pdr_read_p (pdr)) |
2e733703 AK |
82 | { |
83 | if (dump_file) | |
040b0c97 AK |
84 | { |
85 | fprintf (dump_file, "Adding read to depedence graph: "); | |
86 | print_pdr (dump_file, pdr); | |
87 | } | |
adba512d AK |
88 | isl_union_map *um |
89 | = isl_union_map_from_map (add_pdr_constraints (pdr, pbb)); | |
312ce401 | 90 | reads = isl_union_map_union (reads, um); |
040b0c97 AK |
91 | if (dump_file) |
92 | { | |
93 | fprintf (dump_file, "Reads depedence graph: "); | |
312ce401 | 94 | print_isl_union_map (dump_file, reads); |
040b0c97 | 95 | } |
2e733703 | 96 | } |
312ce401 | 97 | else if (pdr_write_p (pdr)) |
2e733703 AK |
98 | { |
99 | if (dump_file) | |
040b0c97 AK |
100 | { |
101 | fprintf (dump_file, "Adding must write to depedence graph: "); | |
102 | print_pdr (dump_file, pdr); | |
103 | } | |
adba512d AK |
104 | isl_union_map *um |
105 | = isl_union_map_from_map (add_pdr_constraints (pdr, pbb)); | |
312ce401 | 106 | must_writes = isl_union_map_union (must_writes, um); |
040b0c97 AK |
107 | if (dump_file) |
108 | { | |
109 | fprintf (dump_file, "Must writes depedence graph: "); | |
312ce401 | 110 | print_isl_union_map (dump_file, must_writes); |
040b0c97 | 111 | } |
2e733703 | 112 | } |
312ce401 | 113 | else if (pdr_may_write_p (pdr)) |
2e733703 AK |
114 | { |
115 | if (dump_file) | |
040b0c97 AK |
116 | { |
117 | fprintf (dump_file, "Adding may write to depedence graph: "); | |
118 | print_pdr (dump_file, pdr); | |
119 | } | |
adba512d AK |
120 | isl_union_map *um |
121 | = isl_union_map_from_map (add_pdr_constraints (pdr, pbb)); | |
312ce401 | 122 | may_writes = isl_union_map_union (may_writes, um); |
040b0c97 AK |
123 | if (dump_file) |
124 | { | |
125 | fprintf (dump_file, "May writes depedence graph: "); | |
312ce401 | 126 | print_isl_union_map (dump_file, may_writes); |
040b0c97 | 127 | } |
2e733703 | 128 | } |
312ce401 | 129 | } |
7cbd4c5e | 130 | } |
2abae5f1 SP |
131 | } |
132 | ||
33ad93b9 RG |
133 | /* Helper function used on each MAP of a isl_union_map. Computes the |
134 | maximal output dimension. */ | |
60d2a8c3 | 135 | |
32400032 | 136 | static isl_stat |
33ad93b9 | 137 | max_number_of_out_dimensions (__isl_take isl_map *map, void *user) |
60d2a8c3 | 138 | { |
33ad93b9 RG |
139 | int global_max = *((int *) user); |
140 | isl_space *space = isl_map_get_space (map); | |
141 | int nb_out = isl_space_dim (space, isl_dim_out); | |
60d2a8c3 | 142 | |
33ad93b9 RG |
143 | if (global_max < nb_out) |
144 | *((int *) user) = nb_out; | |
60d2a8c3 | 145 | |
33ad93b9 RG |
146 | isl_map_free (map); |
147 | isl_space_free (space); | |
32400032 | 148 | return isl_stat_ok; |
60d2a8c3 SP |
149 | } |
150 | ||
33ad93b9 | 151 | /* Extends the output dimension of MAP to MAX dimensions. */ |
60d2a8c3 | 152 | |
33ad93b9 RG |
153 | static __isl_give isl_map * |
154 | extend_map (__isl_take isl_map *map, int max) | |
60d2a8c3 | 155 | { |
33ad93b9 RG |
156 | isl_space *space = isl_map_get_space (map); |
157 | int n = isl_space_dim (space, isl_dim_out); | |
b5eb099f | 158 | |
33ad93b9 RG |
159 | isl_space_free (space); |
160 | return isl_map_add_dims (map, isl_dim_out, max - n); | |
60d2a8c3 SP |
161 | } |
162 | ||
33ad93b9 | 163 | /* Structure used to pass parameters to extend_schedule_1. */ |
e37f165f | 164 | |
33ad93b9 RG |
165 | struct extend_schedule_str { |
166 | int max; | |
167 | isl_union_map *umap; | |
168 | }; | |
2abae5f1 | 169 | |
33ad93b9 | 170 | /* Helper function for extend_schedule. */ |
a0dd1440 | 171 | |
32400032 | 172 | static isl_stat |
33ad93b9 | 173 | extend_schedule_1 (__isl_take isl_map *map, void *user) |
a0dd1440 | 174 | { |
33ad93b9 RG |
175 | struct extend_schedule_str *str = (struct extend_schedule_str *) user; |
176 | str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max)); | |
32400032 | 177 | return isl_stat_ok; |
a0dd1440 SP |
178 | } |
179 | ||
33ad93b9 | 180 | /* Return a relation that has uniform output dimensions. */ |
2abae5f1 | 181 | |
01bdcc80 | 182 | static __isl_give isl_union_map * |
33ad93b9 | 183 | extend_schedule (__isl_take isl_union_map *x) |
2abae5f1 | 184 | { |
33ad93b9 | 185 | int max = 0; |
33ad93b9 | 186 | struct extend_schedule_str str; |
2abae5f1 | 187 | |
6b3ebcdd | 188 | isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max); |
33ad93b9 RG |
189 | str.max = max; |
190 | str.umap = isl_union_map_empty (isl_union_map_get_space (x)); | |
6b3ebcdd | 191 | isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str); |
33ad93b9 | 192 | isl_union_map_free (x); |
14b1747c | 193 | return isl_union_map_coalesce (str.umap); |
2abae5f1 SP |
194 | } |
195 | ||
33ad93b9 RG |
196 | /* Applies SCHEDULE to the in and out dimensions of the dependences |
197 | DEPS and return the resulting relation. */ | |
2abae5f1 | 198 | |
33ad93b9 RG |
199 | static isl_map * |
200 | apply_schedule_on_deps (__isl_keep isl_union_map *schedule, | |
201 | __isl_keep isl_union_map *deps) | |
2abae5f1 | 202 | { |
14b1747c AK |
203 | isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule)); |
204 | isl_union_map *ux = isl_union_map_copy (deps); | |
33ad93b9 RG |
205 | ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans)); |
206 | ux = isl_union_map_apply_range (ux, trans); | |
14b1747c AK |
207 | ux = isl_union_map_coalesce (ux); |
208 | ||
209 | if (!isl_union_map_is_empty (ux)) | |
210 | return isl_map_from_union_map (ux); | |
2abae5f1 | 211 | |
14b1747c AK |
212 | isl_union_map_free (ux); |
213 | return NULL; | |
2abae5f1 SP |
214 | } |
215 | ||
33ad93b9 RG |
216 | /* Return true when DEPS is non empty and the intersection of LEX with |
217 | the DEPS transformed by SCHEDULE is non empty. LEX is the relation | |
218 | in which all the inputs before DEPTH occur at the same time as the | |
219 | output, and the input at DEPTH occurs before output. */ | |
2abae5f1 | 220 | |
574921c2 | 221 | bool |
33ad93b9 RG |
222 | carries_deps (__isl_keep isl_union_map *schedule, |
223 | __isl_keep isl_union_map *deps, | |
224 | int depth) | |
2abae5f1 | 225 | { |
33ad93b9 RG |
226 | if (isl_union_map_is_empty (deps)) |
227 | return false; | |
2abae5f1 | 228 | |
14b1747c | 229 | isl_map *x = apply_schedule_on_deps (schedule, deps); |
574921c2 RG |
230 | if (x == NULL) |
231 | return false; | |
33ad93b9 | 232 | |
14b1747c AK |
233 | isl_space *space = isl_map_get_space (x); |
234 | isl_map *lex = isl_map_lex_le (isl_space_range (space)); | |
235 | isl_constraint *ineq = isl_inequality_alloc | |
236 | (isl_local_space_from_space (isl_map_get_space (x))); | |
237 | ||
238 | for (int i = 0; i < depth - 1; i++) | |
33ad93b9 RG |
239 | lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i); |
240 | ||
241 | /* in + 1 <= out */ | |
52d676b6 TG |
242 | ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1); |
243 | ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1); | |
33ad93b9 RG |
244 | ineq = isl_constraint_set_constant_si (ineq, -1); |
245 | lex = isl_map_add_constraint (lex, ineq); | |
14b1747c | 246 | lex = isl_map_coalesce (lex); |
33ad93b9 | 247 | x = isl_map_intersect (x, lex); |
14b1747c | 248 | bool res = !isl_map_is_empty (x); |
33ad93b9 RG |
249 | |
250 | isl_map_free (x); | |
251 | return res; | |
2abae5f1 SP |
252 | } |
253 | ||
adba512d AK |
254 | /* Compute the dependence relations for the SCOP: |
255 | RAW are read after write dependences, | |
256 | WAR are write after read dependences, | |
257 | WAW are write after write dependences. */ | |
258 | ||
259 | void | |
260 | scop_get_dependences (scop_p scop) | |
261 | { | |
262 | if (scop->dependence) | |
263 | return; | |
264 | ||
312ce401 SP |
265 | isl_space *space = isl_set_get_space (scop->param_context); |
266 | isl_union_map *reads = isl_union_map_empty (isl_space_copy (space)); | |
267 | isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space)); | |
268 | isl_union_map *may_writes = isl_union_map_empty (space); | |
269 | scop_get_reads_and_writes (scop, reads, must_writes, may_writes); | |
adba512d AK |
270 | |
271 | if (dump_file) | |
272 | { | |
273 | fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n"); | |
274 | fprintf (dump_file, "Statements on the iteration domain are mapped to" | |
275 | " array references.\n"); | |
276 | fprintf (dump_file, " To read the following data references:\n\n"); | |
277 | fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n"); | |
278 | fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n"); | |
279 | ||
280 | fprintf (dump_file, " S_5[i0] is the dynamic instance of statement" | |
281 | " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n"); | |
282 | fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1" | |
283 | " and first subscript access i0.\n"); | |
284 | fprintf (dump_file, " [106] is a 'scalar reference' which is the sum of" | |
285 | " SSA_NAME_VERSION 6" | |
286 | " and --param graphite-max-arrays-per-scop=100\n"); | |
287 | fprintf (dump_file, "-----------------------\n\n"); | |
288 | ||
289 | fprintf (dump_file, "data references (\n"); | |
290 | fprintf (dump_file, " reads: "); | |
291 | print_isl_union_map (dump_file, reads); | |
292 | fprintf (dump_file, " must_writes: "); | |
293 | print_isl_union_map (dump_file, must_writes); | |
294 | fprintf (dump_file, " may_writes: "); | |
295 | print_isl_union_map (dump_file, may_writes); | |
296 | fprintf (dump_file, ")\n"); | |
297 | } | |
298 | ||
299 | gcc_assert (scop->original_schedule); | |
300 | ||
301 | isl_union_access_info *ai; | |
302 | ai = isl_union_access_info_from_sink (isl_union_map_copy (reads)); | |
303 | ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes)); | |
304 | ai = isl_union_access_info_set_may_source (ai, may_writes); | |
305 | ai = isl_union_access_info_set_schedule | |
306 | (ai, isl_schedule_copy (scop->original_schedule)); | |
307 | isl_union_flow *flow = isl_union_access_info_compute_flow (ai); | |
308 | isl_union_map *raw = isl_union_flow_get_must_dependence (flow); | |
309 | isl_union_flow_free (flow); | |
310 | ||
311 | ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes)); | |
312 | ai = isl_union_access_info_set_must_source (ai, must_writes); | |
313 | ai = isl_union_access_info_set_may_source (ai, reads); | |
314 | ai = isl_union_access_info_set_schedule | |
315 | (ai, isl_schedule_copy (scop->original_schedule)); | |
316 | flow = isl_union_access_info_compute_flow (ai); | |
317 | ||
318 | isl_union_map *waw = isl_union_flow_get_must_dependence (flow); | |
319 | isl_union_map *war = isl_union_flow_get_may_dependence (flow); | |
320 | war = isl_union_map_subtract (war, isl_union_map_copy (waw)); | |
321 | isl_union_flow_free (flow); | |
322 | ||
323 | raw = isl_union_map_coalesce (raw); | |
324 | waw = isl_union_map_coalesce (waw); | |
325 | war = isl_union_map_coalesce (war); | |
326 | ||
327 | isl_union_map *dependences = raw; | |
328 | dependences = isl_union_map_union (dependences, war); | |
329 | dependences = isl_union_map_union (dependences, waw); | |
330 | dependences = isl_union_map_coalesce (dependences); | |
331 | ||
332 | if (dump_file) | |
333 | { | |
334 | fprintf (dump_file, "data dependences (\n"); | |
335 | print_isl_union_map (dump_file, dependences); | |
336 | fprintf (dump_file, ")\n"); | |
337 | } | |
338 | ||
339 | scop->dependence = dependences; | |
340 | } | |
341 | ||
9c358739 | 342 | #endif /* HAVE_isl */ |