]>
Commit | Line | Data |
---|---|---|
c6bb733d | 1 | /* Data dependence analysis for Graphite. |
f1717362 | 2 | Copyright (C) 2009-2016 Free Software Foundation, Inc. |
c6bb733d | 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 | ||
d8a2c81e | 22 | #define USES_ISL |
23 | ||
c6bb733d | 24 | #include "config.h" |
87e20041 | 25 | |
429cca51 | 26 | #ifdef HAVE_isl |
87e20041 | 27 | |
c6bb733d | 28 | #include "system.h" |
29 | #include "coretypes.h" | |
9ef16211 | 30 | #include "backend.h" |
d040a5b0 | 31 | #include "cfghooks.h" |
b20a8bb4 | 32 | #include "tree.h" |
9ef16211 | 33 | #include "gimple.h" |
9ef16211 | 34 | #include "fold-const.h" |
dcf1a1ec | 35 | #include "gimple-iterator.h" |
073c1fd5 | 36 | #include "tree-ssa-loop.h" |
f0a18dd2 | 37 | #include "tree-pass.h" |
c6bb733d | 38 | #include "cfgloop.h" |
c6bb733d | 39 | #include "tree-data-ref.h" |
39b8c5f3 | 40 | #include "graphite.h" |
0d6b5db2 | 41 | |
87e20041 | 42 | /* Add the constraints from the set S to the domain of MAP. */ |
c6bb733d | 43 | |
87e20041 | 44 | static isl_map * |
45 | constrain_domain (isl_map *map, isl_set *s) | |
0d6b5db2 | 46 | { |
87e20041 | 47 | isl_space *d = isl_map_get_space (map); |
48 | isl_id *id = isl_space_get_tuple_id (d, isl_dim_in); | |
a071b80b | 49 | |
87e20041 | 50 | s = isl_set_set_tuple_id (s, id); |
51 | isl_space_free (d); | |
52 | return isl_map_intersect_domain (map, s); | |
a071b80b | 53 | } |
54 | ||
fc25c670 | 55 | /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain. */ |
a071b80b | 56 | |
87e20041 | 57 | static isl_map * |
58 | add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb) | |
a071b80b | 59 | { |
87e20041 | 60 | isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses), |
fc25c670 | 61 | isl_set_copy (pdr->subscript_sizes)); |
87e20041 | 62 | x = constrain_domain (x, isl_set_copy (pbb->domain)); |
63 | return x; | |
a071b80b | 64 | } |
65 | ||
87e20041 | 66 | /* Returns all the memory reads in SCOP. */ |
a071b80b | 67 | |
87e20041 | 68 | static isl_union_map * |
f1f41a6c | 69 | scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs) |
a071b80b | 70 | { |
87e20041 | 71 | int i, j; |
72 | poly_bb_p pbb; | |
73 | poly_dr_p pdr; | |
3b9ce1aa | 74 | isl_space *space = isl_set_get_space (scop->param_context); |
87e20041 | 75 | isl_union_map *res = isl_union_map_empty (space); |
a071b80b | 76 | |
f1f41a6c | 77 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
0d6b5db2 | 78 | { |
f1f41a6c | 79 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 80 | if (pdr_read_p (pdr)) |
fead8d0e | 81 | { |
82 | if (dump_file) | |
6fb10557 | 83 | { |
84 | fprintf (dump_file, "Adding read to depedence graph: "); | |
85 | print_pdr (dump_file, pdr); | |
86 | } | |
fead8d0e | 87 | res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); |
6fb10557 | 88 | if (dump_file) |
89 | { | |
90 | fprintf (dump_file, "Reads depedence graph: "); | |
91 | print_isl_union_map (dump_file, res); | |
92 | } | |
fead8d0e | 93 | } |
0d6b5db2 | 94 | } |
95 | ||
c6bb733d | 96 | return res; |
97 | } | |
98 | ||
87e20041 | 99 | /* Returns all the memory must writes in SCOP. */ |
c6bb733d | 100 | |
87e20041 | 101 | static isl_union_map * |
f1f41a6c | 102 | scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs) |
c6bb733d | 103 | { |
87e20041 | 104 | int i, j; |
105 | poly_bb_p pbb; | |
106 | poly_dr_p pdr; | |
3b9ce1aa | 107 | isl_space *space = isl_set_get_space (scop->param_context); |
87e20041 | 108 | isl_union_map *res = isl_union_map_empty (space); |
c6bb733d | 109 | |
f1f41a6c | 110 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
c6bb733d | 111 | { |
f1f41a6c | 112 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 113 | if (pdr_write_p (pdr)) |
fead8d0e | 114 | { |
115 | if (dump_file) | |
6fb10557 | 116 | { |
117 | fprintf (dump_file, "Adding must write to depedence graph: "); | |
118 | print_pdr (dump_file, pdr); | |
119 | } | |
fead8d0e | 120 | res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); |
6fb10557 | 121 | if (dump_file) |
122 | { | |
123 | fprintf (dump_file, "Must writes depedence graph: "); | |
124 | print_isl_union_map (dump_file, res); | |
125 | } | |
fead8d0e | 126 | } |
c6bb733d | 127 | } |
128 | ||
c6bb733d | 129 | return res; |
130 | } | |
131 | ||
87e20041 | 132 | /* Returns all the memory may writes in SCOP. */ |
c6bb733d | 133 | |
87e20041 | 134 | static isl_union_map * |
f1f41a6c | 135 | scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs) |
87e20041 | 136 | { |
137 | int i, j; | |
138 | poly_bb_p pbb; | |
139 | poly_dr_p pdr; | |
3b9ce1aa | 140 | isl_space *space = isl_set_get_space (scop->param_context); |
87e20041 | 141 | isl_union_map *res = isl_union_map_empty (space); |
c6bb733d | 142 | |
f1f41a6c | 143 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
abc97125 | 144 | { |
f1f41a6c | 145 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 146 | if (pdr_may_write_p (pdr)) |
fead8d0e | 147 | { |
148 | if (dump_file) | |
6fb10557 | 149 | { |
150 | fprintf (dump_file, "Adding may write to depedence graph: "); | |
151 | print_pdr (dump_file, pdr); | |
152 | } | |
fead8d0e | 153 | res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); |
6fb10557 | 154 | if (dump_file) |
155 | { | |
156 | fprintf (dump_file, "May writes depedence graph: "); | |
157 | print_isl_union_map (dump_file, res); | |
158 | } | |
fead8d0e | 159 | } |
abc97125 | 160 | } |
c6bb733d | 161 | |
c6bb733d | 162 | return res; |
163 | } | |
164 | ||
87e20041 | 165 | /* Returns all the original schedules in SCOP. */ |
b7ac929d | 166 | |
87e20041 | 167 | static isl_union_map * |
f1f41a6c | 168 | scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs) |
87e20041 | 169 | { |
170 | int i; | |
171 | poly_bb_p pbb; | |
3b9ce1aa | 172 | isl_space *space = isl_set_get_space (scop->param_context); |
87e20041 | 173 | isl_union_map *res = isl_union_map_empty (space); |
b7ac929d | 174 | |
f1f41a6c | 175 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
c6bb733d | 176 | { |
87e20041 | 177 | res = isl_union_map_add_map |
178 | (res, constrain_domain (isl_map_copy (pbb->schedule), | |
179 | isl_set_copy (pbb->domain))); | |
c6bb733d | 180 | } |
a071b80b | 181 | |
b7ac929d | 182 | return res; |
c6bb733d | 183 | } |
184 | ||
87e20041 | 185 | /* Helper function used on each MAP of a isl_union_map. Computes the |
186 | maximal output dimension. */ | |
f007fe97 | 187 | |
a26dad6a | 188 | static isl_stat |
87e20041 | 189 | max_number_of_out_dimensions (__isl_take isl_map *map, void *user) |
f007fe97 | 190 | { |
87e20041 | 191 | int global_max = *((int *) user); |
192 | isl_space *space = isl_map_get_space (map); | |
193 | int nb_out = isl_space_dim (space, isl_dim_out); | |
f007fe97 | 194 | |
87e20041 | 195 | if (global_max < nb_out) |
196 | *((int *) user) = nb_out; | |
f007fe97 | 197 | |
87e20041 | 198 | isl_map_free (map); |
199 | isl_space_free (space); | |
a26dad6a | 200 | return isl_stat_ok; |
f007fe97 | 201 | } |
202 | ||
87e20041 | 203 | /* Extends the output dimension of MAP to MAX dimensions. */ |
f007fe97 | 204 | |
87e20041 | 205 | static __isl_give isl_map * |
206 | extend_map (__isl_take isl_map *map, int max) | |
f007fe97 | 207 | { |
87e20041 | 208 | isl_space *space = isl_map_get_space (map); |
209 | int n = isl_space_dim (space, isl_dim_out); | |
a071b80b | 210 | |
87e20041 | 211 | isl_space_free (space); |
212 | return isl_map_add_dims (map, isl_dim_out, max - n); | |
f007fe97 | 213 | } |
214 | ||
87e20041 | 215 | /* Structure used to pass parameters to extend_schedule_1. */ |
0d6b5db2 | 216 | |
87e20041 | 217 | struct extend_schedule_str { |
218 | int max; | |
219 | isl_union_map *umap; | |
220 | }; | |
c6bb733d | 221 | |
87e20041 | 222 | /* Helper function for extend_schedule. */ |
30f4f4a6 | 223 | |
a26dad6a | 224 | static isl_stat |
87e20041 | 225 | extend_schedule_1 (__isl_take isl_map *map, void *user) |
30f4f4a6 | 226 | { |
87e20041 | 227 | struct extend_schedule_str *str = (struct extend_schedule_str *) user; |
228 | str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max)); | |
a26dad6a | 229 | return isl_stat_ok; |
30f4f4a6 | 230 | } |
231 | ||
87e20041 | 232 | /* Return a relation that has uniform output dimensions. */ |
c6bb733d | 233 | |
7a833a09 | 234 | static __isl_give isl_union_map * |
87e20041 | 235 | extend_schedule (__isl_take isl_union_map *x) |
c6bb733d | 236 | { |
87e20041 | 237 | int max = 0; |
87e20041 | 238 | struct extend_schedule_str str; |
c6bb733d | 239 | |
36620673 | 240 | isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max); |
87e20041 | 241 | str.max = max; |
242 | str.umap = isl_union_map_empty (isl_union_map_get_space (x)); | |
36620673 | 243 | isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str); |
87e20041 | 244 | isl_union_map_free (x); |
245 | return str.umap; | |
c6bb733d | 246 | } |
247 | ||
87e20041 | 248 | /* Applies SCHEDULE to the in and out dimensions of the dependences |
249 | DEPS and return the resulting relation. */ | |
c6bb733d | 250 | |
87e20041 | 251 | static isl_map * |
252 | apply_schedule_on_deps (__isl_keep isl_union_map *schedule, | |
253 | __isl_keep isl_union_map *deps) | |
c6bb733d | 254 | { |
87e20041 | 255 | isl_map *x; |
256 | isl_union_map *ux, *trans; | |
c6bb733d | 257 | |
87e20041 | 258 | trans = isl_union_map_copy (schedule); |
259 | trans = extend_schedule (trans); | |
260 | ux = isl_union_map_copy (deps); | |
261 | ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans)); | |
262 | ux = isl_union_map_apply_range (ux, trans); | |
86e09dcd | 263 | if (isl_union_map_is_empty (ux)) |
264 | { | |
265 | isl_union_map_free (ux); | |
266 | return NULL; | |
267 | } | |
87e20041 | 268 | x = isl_map_from_union_map (ux); |
c6bb733d | 269 | |
87e20041 | 270 | return x; |
c6bb733d | 271 | } |
272 | ||
87e20041 | 273 | /* Return true when DEPS is non empty and the intersection of LEX with |
274 | the DEPS transformed by SCHEDULE is non empty. LEX is the relation | |
275 | in which all the inputs before DEPTH occur at the same time as the | |
276 | output, and the input at DEPTH occurs before output. */ | |
c6bb733d | 277 | |
86e09dcd | 278 | bool |
87e20041 | 279 | carries_deps (__isl_keep isl_union_map *schedule, |
280 | __isl_keep isl_union_map *deps, | |
281 | int depth) | |
c6bb733d | 282 | { |
87e20041 | 283 | bool res; |
bffcae34 | 284 | int i; |
87e20041 | 285 | isl_space *space; |
286 | isl_map *lex, *x; | |
287 | isl_constraint *ineq; | |
c6bb733d | 288 | |
87e20041 | 289 | if (isl_union_map_is_empty (deps)) |
290 | return false; | |
c6bb733d | 291 | |
87e20041 | 292 | x = apply_schedule_on_deps (schedule, deps); |
86e09dcd | 293 | if (x == NULL) |
294 | return false; | |
87e20041 | 295 | space = isl_map_get_space (x); |
296 | space = isl_space_range (space); | |
297 | lex = isl_map_lex_le (space); | |
298 | space = isl_map_get_space (x); | |
299 | ineq = isl_inequality_alloc (isl_local_space_from_space (space)); | |
300 | ||
bffcae34 | 301 | for (i = 0; i < depth - 1; i++) |
87e20041 | 302 | lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i); |
303 | ||
304 | /* in + 1 <= out */ | |
bffcae34 | 305 | ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1); |
306 | ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1); | |
87e20041 | 307 | ineq = isl_constraint_set_constant_si (ineq, -1); |
308 | lex = isl_map_add_constraint (lex, ineq); | |
309 | x = isl_map_intersect (x, lex); | |
310 | res = !isl_map_is_empty (x); | |
311 | ||
312 | isl_map_free (x); | |
313 | return res; | |
c6bb733d | 314 | } |
315 | ||
87e20041 | 316 | /* Compute the original data dependences in SCOP for all the reads and |
317 | writes in PBBS. */ | |
96b6d5d7 | 318 | |
7a833a09 | 319 | static void |
f1f41a6c | 320 | compute_deps (scop_p scop, vec<poly_bb_p> pbbs, |
87e20041 | 321 | isl_union_map **must_raw, |
322 | isl_union_map **may_raw, | |
323 | isl_union_map **must_raw_no_source, | |
324 | isl_union_map **may_raw_no_source, | |
325 | isl_union_map **must_war, | |
326 | isl_union_map **may_war, | |
327 | isl_union_map **must_war_no_source, | |
328 | isl_union_map **may_war_no_source, | |
329 | isl_union_map **must_waw, | |
330 | isl_union_map **may_waw, | |
331 | isl_union_map **must_waw_no_source, | |
332 | isl_union_map **may_waw_no_source) | |
de38f9c0 | 333 | { |
87e20041 | 334 | isl_union_map *reads = scop_get_reads (scop, pbbs); |
335 | isl_union_map *must_writes = scop_get_must_writes (scop, pbbs); | |
336 | isl_union_map *may_writes = scop_get_may_writes (scop, pbbs); | |
337 | isl_union_map *all_writes = isl_union_map_union | |
338 | (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes)); | |
339 | isl_space *space = isl_union_map_get_space (all_writes); | |
340 | isl_union_map *empty = isl_union_map_empty (space); | |
341 | isl_union_map *original = scop_get_original_schedule (scop, pbbs); | |
87e20041 | 342 | |
fead8d0e | 343 | if (dump_file) |
344 | { | |
345 | fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n"); | |
346 | fprintf (dump_file, "Statements on the iteration domain are mapped to" | |
347 | " array references.\n"); | |
348 | fprintf (dump_file, " To read the following data references:\n\n"); | |
349 | fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n"); | |
350 | fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n"); | |
351 | ||
352 | fprintf (dump_file, " S_5[i0] is the dynamic instance of statement" | |
353 | " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n"); | |
354 | fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1" | |
355 | " and first subscript access i0.\n"); | |
356 | fprintf (dump_file, " [106] is a 'scalar reference' which is the sum of" | |
357 | " SSA_NAME_VERSION 6" | |
358 | " and --param graphite-max-arrays-per-scop=100\n"); | |
359 | fprintf (dump_file, "-----------------------\n\n"); | |
360 | ||
361 | fprintf (dump_file, "data references (\n"); | |
362 | fprintf (dump_file, " reads: "); | |
363 | print_isl_union_map (dump_file, reads); | |
364 | fprintf (dump_file, " must_writes: "); | |
365 | print_isl_union_map (dump_file, must_writes); | |
366 | fprintf (dump_file, " may_writes: "); | |
367 | print_isl_union_map (dump_file, may_writes); | |
368 | fprintf (dump_file, " all_writes: "); | |
369 | print_isl_union_map (dump_file, all_writes); | |
370 | fprintf (dump_file, ")\n"); | |
371 | } | |
372 | ||
36620673 | 373 | isl_union_map_compute_flow (isl_union_map_copy (reads), |
374 | isl_union_map_copy (must_writes), | |
375 | isl_union_map_copy (may_writes), | |
376 | isl_union_map_copy (original), | |
377 | must_raw, may_raw, must_raw_no_source, | |
378 | may_raw_no_source); | |
379 | isl_union_map_compute_flow (isl_union_map_copy (all_writes), | |
380 | reads, empty, | |
381 | isl_union_map_copy (original), | |
382 | must_war, may_war, must_war_no_source, | |
383 | may_war_no_source); | |
384 | isl_union_map_compute_flow (all_writes, must_writes, may_writes, | |
6e33678d | 385 | original, |
36620673 | 386 | must_waw, may_waw, must_waw_no_source, |
387 | may_waw_no_source); | |
de38f9c0 | 388 | } |
389 | ||
7a833a09 | 390 | isl_union_map * |
391 | scop_get_dependences (scop_p scop) | |
392 | { | |
18d73d6f | 393 | if (scop->dependence) |
394 | return scop->dependence; | |
395 | ||
396 | /* The original dependence relations: | |
397 | RAW are read after write dependences, | |
398 | WAR are write after read dependences, | |
399 | WAW are write after write dependences. */ | |
400 | isl_union_map *must_raw = NULL, *may_raw = NULL, *must_raw_no_source = NULL, | |
401 | *may_raw_no_source = NULL, *must_war = NULL, *may_war = NULL, | |
402 | *must_war_no_source = NULL, *may_war_no_source = NULL, *must_waw = NULL, | |
403 | *may_waw = NULL, *must_waw_no_source = NULL, *may_waw_no_source = NULL; | |
404 | ||
405 | compute_deps (scop, scop->pbbs, | |
406 | &must_raw, &may_raw, | |
407 | &must_raw_no_source, &may_raw_no_source, | |
408 | &must_war, &may_war, | |
409 | &must_war_no_source, &may_war_no_source, | |
410 | &must_waw, &may_waw, | |
411 | &must_waw_no_source, &may_waw_no_source); | |
412 | ||
413 | isl_union_map *dependences = must_raw; | |
414 | dependences = isl_union_map_union (dependences, must_war); | |
415 | dependences = isl_union_map_union (dependences, must_waw); | |
416 | dependences = isl_union_map_union (dependences, may_raw); | |
417 | dependences = isl_union_map_union (dependences, may_war); | |
418 | dependences = isl_union_map_union (dependences, may_waw); | |
7a833a09 | 419 | |
d9ac4c34 | 420 | if (dump_file) |
421 | { | |
422 | fprintf (dump_file, "data dependences (\n"); | |
423 | print_isl_union_map (dump_file, dependences); | |
424 | fprintf (dump_file, ")\n"); | |
425 | } | |
426 | ||
18d73d6f | 427 | isl_union_map_free (must_raw_no_source); |
428 | isl_union_map_free (may_raw_no_source); | |
429 | isl_union_map_free (must_war_no_source); | |
430 | isl_union_map_free (may_war_no_source); | |
431 | isl_union_map_free (must_waw_no_source); | |
432 | isl_union_map_free (may_waw_no_source); | |
433 | ||
434 | scop->dependence = dependences; | |
7a833a09 | 435 | return dependences; |
436 | } | |
437 | ||
26bd1f19 | 438 | #endif /* HAVE_isl */ |