]>
Commit | Line | Data |
---|---|---|
c6bb733d | 1 | /* Data dependence analysis for Graphite. |
d353bf18 | 2 | Copyright (C) 2009-2015 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 | ||
22 | #include "config.h" | |
87e20041 | 23 | |
429cca51 | 24 | #ifdef HAVE_isl |
87e20041 | 25 | #include <isl/set.h> |
26 | #include <isl/map.h> | |
27 | #include <isl/union_map.h> | |
28 | #include <isl/flow.h> | |
29 | #include <isl/constraint.h> | |
429cca51 | 30 | #endif |
87e20041 | 31 | |
c6bb733d | 32 | #include "system.h" |
33 | #include "coretypes.h" | |
b20a8bb4 | 34 | #include "input.h" |
35 | #include "alias.h" | |
36 | #include "symtab.h" | |
37 | #include "options.h" | |
b20a8bb4 | 38 | #include "tree.h" |
39 | #include "fold-const.h" | |
40 | #include "predict.h" | |
94ea8568 | 41 | #include "tm.h" |
42 | #include "hard-reg-set.h" | |
43 | #include "input.h" | |
44 | #include "function.h" | |
45 | #include "dominance.h" | |
46 | #include "cfg.h" | |
bc61cadb | 47 | #include "basic-block.h" |
48 | #include "tree-ssa-alias.h" | |
49 | #include "internal-fn.h" | |
50 | #include "gimple-expr.h" | |
51 | #include "is-a.h" | |
073c1fd5 | 52 | #include "gimple.h" |
dcf1a1ec | 53 | #include "gimple-iterator.h" |
073c1fd5 | 54 | #include "tree-ssa-loop.h" |
f0a18dd2 | 55 | #include "tree-pass.h" |
c6bb733d | 56 | #include "cfgloop.h" |
57 | #include "tree-chrec.h" | |
58 | #include "tree-data-ref.h" | |
59 | #include "tree-scalar-evolution.h" | |
1e5b7b1f | 60 | #include "sese.h" |
c6bb733d | 61 | |
429cca51 | 62 | #ifdef HAVE_isl |
c6bb733d | 63 | #include "graphite-poly.h" |
0d6b5db2 | 64 | |
86e09dcd | 65 | isl_union_map * |
66 | scop_get_dependences (scop_p scop) | |
67 | { | |
68 | isl_union_map *dependences; | |
69 | ||
70 | if (!scop->must_raw) | |
71 | compute_deps (scop, SCOP_BBS (scop), | |
72 | &scop->must_raw, &scop->may_raw, | |
73 | &scop->must_raw_no_source, &scop->may_raw_no_source, | |
74 | &scop->must_war, &scop->may_war, | |
75 | &scop->must_war_no_source, &scop->may_war_no_source, | |
76 | &scop->must_waw, &scop->may_waw, | |
77 | &scop->must_waw_no_source, &scop->may_waw_no_source); | |
78 | ||
79 | dependences = isl_union_map_copy (scop->must_raw); | |
80 | dependences = isl_union_map_union (dependences, | |
81 | isl_union_map_copy (scop->must_war)); | |
82 | dependences = isl_union_map_union (dependences, | |
83 | isl_union_map_copy (scop->must_waw)); | |
84 | dependences = isl_union_map_union (dependences, | |
85 | isl_union_map_copy (scop->may_raw)); | |
86 | dependences = isl_union_map_union (dependences, | |
87 | isl_union_map_copy (scop->may_war)); | |
88 | dependences = isl_union_map_union (dependences, | |
89 | isl_union_map_copy (scop->may_waw)); | |
90 | ||
91 | return dependences; | |
92 | } | |
93 | ||
87e20041 | 94 | /* Add the constraints from the set S to the domain of MAP. */ |
c6bb733d | 95 | |
87e20041 | 96 | static isl_map * |
97 | constrain_domain (isl_map *map, isl_set *s) | |
0d6b5db2 | 98 | { |
87e20041 | 99 | isl_space *d = isl_map_get_space (map); |
100 | isl_id *id = isl_space_get_tuple_id (d, isl_dim_in); | |
a071b80b | 101 | |
87e20041 | 102 | s = isl_set_set_tuple_id (s, id); |
103 | isl_space_free (d); | |
104 | return isl_map_intersect_domain (map, s); | |
a071b80b | 105 | } |
106 | ||
87e20041 | 107 | /* Constrain pdr->accesses with pdr->extent and pbb->domain. */ |
a071b80b | 108 | |
87e20041 | 109 | static isl_map * |
110 | add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb) | |
a071b80b | 111 | { |
87e20041 | 112 | isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses), |
113 | isl_set_copy (pdr->extent)); | |
114 | x = constrain_domain (x, isl_set_copy (pbb->domain)); | |
115 | return x; | |
a071b80b | 116 | } |
117 | ||
87e20041 | 118 | /* Returns all the memory reads in SCOP. */ |
a071b80b | 119 | |
87e20041 | 120 | static isl_union_map * |
f1f41a6c | 121 | scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs) |
a071b80b | 122 | { |
87e20041 | 123 | int i, j; |
124 | poly_bb_p pbb; | |
125 | poly_dr_p pdr; | |
126 | isl_space *space = isl_set_get_space (scop->context); | |
127 | isl_union_map *res = isl_union_map_empty (space); | |
a071b80b | 128 | |
f1f41a6c | 129 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
0d6b5db2 | 130 | { |
f1f41a6c | 131 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 132 | if (pdr_read_p (pdr)) |
133 | res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); | |
0d6b5db2 | 134 | } |
135 | ||
c6bb733d | 136 | return res; |
137 | } | |
138 | ||
87e20041 | 139 | /* Returns all the memory must writes in SCOP. */ |
c6bb733d | 140 | |
87e20041 | 141 | static isl_union_map * |
f1f41a6c | 142 | scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs) |
c6bb733d | 143 | { |
87e20041 | 144 | int i, j; |
145 | poly_bb_p pbb; | |
146 | poly_dr_p pdr; | |
147 | isl_space *space = isl_set_get_space (scop->context); | |
148 | isl_union_map *res = isl_union_map_empty (space); | |
c6bb733d | 149 | |
f1f41a6c | 150 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
c6bb733d | 151 | { |
f1f41a6c | 152 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 153 | if (pdr_write_p (pdr)) |
154 | res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); | |
c6bb733d | 155 | } |
156 | ||
c6bb733d | 157 | return res; |
158 | } | |
159 | ||
87e20041 | 160 | /* Returns all the memory may writes in SCOP. */ |
c6bb733d | 161 | |
87e20041 | 162 | static isl_union_map * |
f1f41a6c | 163 | scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs) |
87e20041 | 164 | { |
165 | int i, j; | |
166 | poly_bb_p pbb; | |
167 | poly_dr_p pdr; | |
168 | isl_space *space = isl_set_get_space (scop->context); | |
169 | isl_union_map *res = isl_union_map_empty (space); | |
c6bb733d | 170 | |
f1f41a6c | 171 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
abc97125 | 172 | { |
f1f41a6c | 173 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 174 | if (pdr_may_write_p (pdr)) |
175 | res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); | |
abc97125 | 176 | } |
c6bb733d | 177 | |
c6bb733d | 178 | return res; |
179 | } | |
180 | ||
87e20041 | 181 | /* Returns all the original schedules in SCOP. */ |
b7ac929d | 182 | |
87e20041 | 183 | static isl_union_map * |
f1f41a6c | 184 | scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs) |
87e20041 | 185 | { |
186 | int i; | |
187 | poly_bb_p pbb; | |
188 | isl_space *space = isl_set_get_space (scop->context); | |
189 | isl_union_map *res = isl_union_map_empty (space); | |
b7ac929d | 190 | |
f1f41a6c | 191 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
c6bb733d | 192 | { |
87e20041 | 193 | res = isl_union_map_add_map |
194 | (res, constrain_domain (isl_map_copy (pbb->schedule), | |
195 | isl_set_copy (pbb->domain))); | |
c6bb733d | 196 | } |
a071b80b | 197 | |
b7ac929d | 198 | return res; |
c6bb733d | 199 | } |
200 | ||
87e20041 | 201 | /* Returns all the transformed schedules in SCOP. */ |
c6bb733d | 202 | |
87e20041 | 203 | static isl_union_map * |
f1f41a6c | 204 | scop_get_transformed_schedule (scop_p scop, vec<poly_bb_p> pbbs) |
c6bb733d | 205 | { |
87e20041 | 206 | int i; |
207 | poly_bb_p pbb; | |
208 | isl_space *space = isl_set_get_space (scop->context); | |
209 | isl_union_map *res = isl_union_map_empty (space); | |
8fe76250 | 210 | |
f1f41a6c | 211 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
1877ea6b | 212 | { |
87e20041 | 213 | res = isl_union_map_add_map |
214 | (res, constrain_domain (isl_map_copy (pbb->transformed), | |
215 | isl_set_copy (pbb->domain))); | |
1877ea6b | 216 | } |
c6bb733d | 217 | |
218 | return res; | |
219 | } | |
220 | ||
87e20041 | 221 | /* Helper function used on each MAP of a isl_union_map. Computes the |
222 | maximal output dimension. */ | |
f007fe97 | 223 | |
87e20041 | 224 | static int |
225 | max_number_of_out_dimensions (__isl_take isl_map *map, void *user) | |
f007fe97 | 226 | { |
87e20041 | 227 | int global_max = *((int *) user); |
228 | isl_space *space = isl_map_get_space (map); | |
229 | int nb_out = isl_space_dim (space, isl_dim_out); | |
f007fe97 | 230 | |
87e20041 | 231 | if (global_max < nb_out) |
232 | *((int *) user) = nb_out; | |
f007fe97 | 233 | |
87e20041 | 234 | isl_map_free (map); |
235 | isl_space_free (space); | |
236 | return 0; | |
f007fe97 | 237 | } |
238 | ||
87e20041 | 239 | /* Extends the output dimension of MAP to MAX dimensions. */ |
f007fe97 | 240 | |
87e20041 | 241 | static __isl_give isl_map * |
242 | extend_map (__isl_take isl_map *map, int max) | |
f007fe97 | 243 | { |
87e20041 | 244 | isl_space *space = isl_map_get_space (map); |
245 | int n = isl_space_dim (space, isl_dim_out); | |
a071b80b | 246 | |
87e20041 | 247 | isl_space_free (space); |
248 | return isl_map_add_dims (map, isl_dim_out, max - n); | |
f007fe97 | 249 | } |
250 | ||
87e20041 | 251 | /* Structure used to pass parameters to extend_schedule_1. */ |
0d6b5db2 | 252 | |
87e20041 | 253 | struct extend_schedule_str { |
254 | int max; | |
255 | isl_union_map *umap; | |
256 | }; | |
c6bb733d | 257 | |
87e20041 | 258 | /* Helper function for extend_schedule. */ |
30f4f4a6 | 259 | |
87e20041 | 260 | static int |
261 | extend_schedule_1 (__isl_take isl_map *map, void *user) | |
30f4f4a6 | 262 | { |
87e20041 | 263 | struct extend_schedule_str *str = (struct extend_schedule_str *) user; |
264 | str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max)); | |
265 | return 0; | |
30f4f4a6 | 266 | } |
267 | ||
87e20041 | 268 | /* Return a relation that has uniform output dimensions. */ |
c6bb733d | 269 | |
87e20041 | 270 | __isl_give isl_union_map * |
271 | extend_schedule (__isl_take isl_union_map *x) | |
c6bb733d | 272 | { |
87e20041 | 273 | int max = 0; |
274 | int res; | |
275 | struct extend_schedule_str str; | |
c6bb733d | 276 | |
87e20041 | 277 | res = isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max); |
278 | gcc_assert (res == 0); | |
9e3531b5 | 279 | |
87e20041 | 280 | str.max = max; |
281 | str.umap = isl_union_map_empty (isl_union_map_get_space (x)); | |
282 | res = isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str); | |
283 | gcc_assert (res == 0); | |
9e3531b5 | 284 | |
87e20041 | 285 | isl_union_map_free (x); |
286 | return str.umap; | |
c6bb733d | 287 | } |
288 | ||
87e20041 | 289 | /* Applies SCHEDULE to the in and out dimensions of the dependences |
290 | DEPS and return the resulting relation. */ | |
c6bb733d | 291 | |
87e20041 | 292 | static isl_map * |
293 | apply_schedule_on_deps (__isl_keep isl_union_map *schedule, | |
294 | __isl_keep isl_union_map *deps) | |
c6bb733d | 295 | { |
87e20041 | 296 | isl_map *x; |
297 | isl_union_map *ux, *trans; | |
c6bb733d | 298 | |
87e20041 | 299 | trans = isl_union_map_copy (schedule); |
300 | trans = extend_schedule (trans); | |
301 | ux = isl_union_map_copy (deps); | |
302 | ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans)); | |
303 | ux = isl_union_map_apply_range (ux, trans); | |
86e09dcd | 304 | if (isl_union_map_is_empty (ux)) |
305 | { | |
306 | isl_union_map_free (ux); | |
307 | return NULL; | |
308 | } | |
87e20041 | 309 | x = isl_map_from_union_map (ux); |
c6bb733d | 310 | |
87e20041 | 311 | return x; |
c6bb733d | 312 | } |
313 | ||
87e20041 | 314 | /* Return true when SCHEDULE does not violate the data DEPS: that is |
315 | when the intersection of LEX with the DEPS transformed by SCHEDULE | |
316 | is empty. LEX is the relation in which the outputs occur before | |
317 | the inputs. */ | |
c6bb733d | 318 | |
319 | static bool | |
87e20041 | 320 | no_violations (__isl_keep isl_union_map *schedule, |
321 | __isl_keep isl_union_map *deps) | |
c6bb733d | 322 | { |
87e20041 | 323 | bool res; |
324 | isl_space *space; | |
325 | isl_map *lex, *x; | |
8fe76250 | 326 | |
87e20041 | 327 | if (isl_union_map_is_empty (deps)) |
328 | return true; | |
c6bb733d | 329 | |
87e20041 | 330 | x = apply_schedule_on_deps (schedule, deps); |
331 | space = isl_map_get_space (x); | |
332 | space = isl_space_range (space); | |
333 | lex = isl_map_lex_ge (space); | |
334 | x = isl_map_intersect (x, lex); | |
335 | res = isl_map_is_empty (x); | |
a071b80b | 336 | |
87e20041 | 337 | isl_map_free (x); |
338 | return res; | |
c6bb733d | 339 | } |
340 | ||
87e20041 | 341 | /* Return true when DEPS is non empty and the intersection of LEX with |
342 | the DEPS transformed by SCHEDULE is non empty. LEX is the relation | |
343 | in which all the inputs before DEPTH occur at the same time as the | |
344 | output, and the input at DEPTH occurs before output. */ | |
c6bb733d | 345 | |
86e09dcd | 346 | bool |
87e20041 | 347 | carries_deps (__isl_keep isl_union_map *schedule, |
348 | __isl_keep isl_union_map *deps, | |
349 | int depth) | |
c6bb733d | 350 | { |
87e20041 | 351 | bool res; |
bffcae34 | 352 | int i; |
87e20041 | 353 | isl_space *space; |
354 | isl_map *lex, *x; | |
355 | isl_constraint *ineq; | |
c6bb733d | 356 | |
87e20041 | 357 | if (isl_union_map_is_empty (deps)) |
358 | return false; | |
c6bb733d | 359 | |
87e20041 | 360 | x = apply_schedule_on_deps (schedule, deps); |
86e09dcd | 361 | if (x == NULL) |
362 | return false; | |
87e20041 | 363 | space = isl_map_get_space (x); |
364 | space = isl_space_range (space); | |
365 | lex = isl_map_lex_le (space); | |
366 | space = isl_map_get_space (x); | |
367 | ineq = isl_inequality_alloc (isl_local_space_from_space (space)); | |
368 | ||
bffcae34 | 369 | for (i = 0; i < depth - 1; i++) |
87e20041 | 370 | lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i); |
371 | ||
372 | /* in + 1 <= out */ | |
bffcae34 | 373 | ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1); |
374 | ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1); | |
87e20041 | 375 | ineq = isl_constraint_set_constant_si (ineq, -1); |
376 | lex = isl_map_add_constraint (lex, ineq); | |
377 | x = isl_map_intersect (x, lex); | |
378 | res = !isl_map_is_empty (x); | |
379 | ||
380 | isl_map_free (x); | |
381 | return res; | |
c6bb733d | 382 | } |
383 | ||
87e20041 | 384 | /* Subtract from the RAW, WAR, and WAW dependences those relations |
385 | that have been marked as belonging to an associative commutative | |
386 | reduction. */ | |
a7d089ac | 387 | |
388 | static void | |
87e20041 | 389 | subtract_commutative_associative_deps (scop_p scop, |
f1f41a6c | 390 | vec<poly_bb_p> pbbs, |
87e20041 | 391 | isl_union_map *original, |
392 | isl_union_map **must_raw, | |
393 | isl_union_map **may_raw, | |
394 | isl_union_map **must_raw_no_source, | |
395 | isl_union_map **may_raw_no_source, | |
396 | isl_union_map **must_war, | |
397 | isl_union_map **may_war, | |
398 | isl_union_map **must_war_no_source, | |
399 | isl_union_map **may_war_no_source, | |
400 | isl_union_map **must_waw, | |
401 | isl_union_map **may_waw, | |
402 | isl_union_map **must_waw_no_source, | |
403 | isl_union_map **may_waw_no_source) | |
de38f9c0 | 404 | { |
87e20041 | 405 | int i, j; |
406 | poly_bb_p pbb; | |
407 | poly_dr_p pdr; | |
408 | isl_space *space = isl_set_get_space (scop->context); | |
de38f9c0 | 409 | |
f1f41a6c | 410 | FOR_EACH_VEC_ELT (pbbs, i, pbb) |
87e20041 | 411 | if (PBB_IS_REDUCTION (pbb)) |
de38f9c0 | 412 | { |
87e20041 | 413 | int res; |
414 | isl_union_map *r = isl_union_map_empty (isl_space_copy (space)); | |
415 | isl_union_map *must_w = isl_union_map_empty (isl_space_copy (space)); | |
416 | isl_union_map *may_w = isl_union_map_empty (isl_space_copy (space)); | |
417 | isl_union_map *all_w; | |
418 | isl_union_map *empty; | |
419 | isl_union_map *x_must_raw; | |
420 | isl_union_map *x_may_raw; | |
421 | isl_union_map *x_must_raw_no_source; | |
422 | isl_union_map *x_may_raw_no_source; | |
423 | isl_union_map *x_must_war; | |
424 | isl_union_map *x_may_war; | |
425 | isl_union_map *x_must_war_no_source; | |
426 | isl_union_map *x_may_war_no_source; | |
427 | isl_union_map *x_must_waw; | |
428 | isl_union_map *x_may_waw; | |
429 | isl_union_map *x_must_waw_no_source; | |
430 | isl_union_map *x_may_waw_no_source; | |
431 | ||
f1f41a6c | 432 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 433 | if (pdr_read_p (pdr)) |
434 | r = isl_union_map_add_map (r, add_pdr_constraints (pdr, pbb)); | |
435 | ||
f1f41a6c | 436 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 437 | if (pdr_write_p (pdr)) |
438 | must_w = isl_union_map_add_map (must_w, | |
439 | add_pdr_constraints (pdr, pbb)); | |
440 | ||
f1f41a6c | 441 | FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) |
87e20041 | 442 | if (pdr_may_write_p (pdr)) |
443 | may_w = isl_union_map_add_map (may_w, | |
444 | add_pdr_constraints (pdr, pbb)); | |
445 | ||
446 | all_w = isl_union_map_union | |
447 | (isl_union_map_copy (must_w), isl_union_map_copy (may_w)); | |
448 | empty = isl_union_map_empty (isl_union_map_get_space (all_w)); | |
449 | ||
450 | res = isl_union_map_compute_flow (isl_union_map_copy (r), | |
451 | isl_union_map_copy (must_w), | |
452 | isl_union_map_copy (may_w), | |
453 | isl_union_map_copy (original), | |
454 | &x_must_raw, &x_may_raw, | |
455 | &x_must_raw_no_source, | |
456 | &x_may_raw_no_source); | |
457 | gcc_assert (res == 0); | |
458 | res = isl_union_map_compute_flow (isl_union_map_copy (all_w), | |
459 | r, empty, | |
460 | isl_union_map_copy (original), | |
461 | &x_must_war, &x_may_war, | |
462 | &x_must_war_no_source, | |
463 | &x_may_war_no_source); | |
464 | gcc_assert (res == 0); | |
465 | res = isl_union_map_compute_flow (all_w, must_w, may_w, | |
466 | isl_union_map_copy (original), | |
467 | &x_must_waw, &x_may_waw, | |
468 | &x_must_waw_no_source, | |
469 | &x_may_waw_no_source); | |
470 | gcc_assert (res == 0); | |
471 | ||
8131b78c | 472 | if (must_raw) |
473 | *must_raw = isl_union_map_subtract (*must_raw, x_must_raw); | |
474 | else | |
475 | isl_union_map_free (x_must_raw); | |
476 | ||
477 | if (may_raw) | |
478 | *may_raw = isl_union_map_subtract (*may_raw, x_may_raw); | |
479 | else | |
480 | isl_union_map_free (x_may_raw); | |
481 | ||
482 | if (must_raw_no_source) | |
483 | *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source, | |
484 | x_must_raw_no_source); | |
485 | else | |
486 | isl_union_map_free (x_must_raw_no_source); | |
487 | ||
488 | if (may_raw_no_source) | |
489 | *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source, | |
490 | x_may_raw_no_source); | |
491 | else | |
492 | isl_union_map_free (x_may_raw_no_source); | |
493 | ||
494 | if (must_war) | |
495 | *must_war = isl_union_map_subtract (*must_war, x_must_war); | |
496 | else | |
497 | isl_union_map_free (x_must_war); | |
498 | ||
499 | if (may_war) | |
500 | *may_war = isl_union_map_subtract (*may_war, x_may_war); | |
501 | else | |
502 | isl_union_map_free (x_may_war); | |
503 | ||
504 | if (must_war_no_source) | |
505 | *must_war_no_source = isl_union_map_subtract (*must_war_no_source, | |
506 | x_must_war_no_source); | |
507 | else | |
508 | isl_union_map_free (x_must_war_no_source); | |
509 | ||
510 | if (may_war_no_source) | |
511 | *may_war_no_source = isl_union_map_subtract (*may_war_no_source, | |
512 | x_may_war_no_source); | |
513 | else | |
514 | isl_union_map_free (x_may_war_no_source); | |
515 | ||
516 | if (must_waw) | |
517 | *must_waw = isl_union_map_subtract (*must_waw, x_must_waw); | |
518 | else | |
519 | isl_union_map_free (x_must_waw); | |
520 | ||
521 | if (may_waw) | |
522 | *may_waw = isl_union_map_subtract (*may_waw, x_may_waw); | |
523 | else | |
524 | isl_union_map_free (x_may_waw); | |
525 | ||
526 | if (must_waw_no_source) | |
527 | *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source, | |
528 | x_must_waw_no_source); | |
529 | else | |
530 | isl_union_map_free (x_must_waw_no_source); | |
531 | ||
532 | if (may_waw_no_source) | |
533 | *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source, | |
534 | x_may_waw_no_source); | |
535 | else | |
536 | isl_union_map_free (x_may_waw_no_source); | |
de38f9c0 | 537 | } |
87e20041 | 538 | |
539 | isl_union_map_free (original); | |
540 | isl_space_free (space); | |
a7d089ac | 541 | } |
542 | ||
87e20041 | 543 | /* Compute the original data dependences in SCOP for all the reads and |
544 | writes in PBBS. */ | |
96b6d5d7 | 545 | |
89049f25 | 546 | void |
f1f41a6c | 547 | compute_deps (scop_p scop, vec<poly_bb_p> pbbs, |
87e20041 | 548 | isl_union_map **must_raw, |
549 | isl_union_map **may_raw, | |
550 | isl_union_map **must_raw_no_source, | |
551 | isl_union_map **may_raw_no_source, | |
552 | isl_union_map **must_war, | |
553 | isl_union_map **may_war, | |
554 | isl_union_map **must_war_no_source, | |
555 | isl_union_map **may_war_no_source, | |
556 | isl_union_map **must_waw, | |
557 | isl_union_map **may_waw, | |
558 | isl_union_map **must_waw_no_source, | |
559 | isl_union_map **may_waw_no_source) | |
de38f9c0 | 560 | { |
87e20041 | 561 | isl_union_map *reads = scop_get_reads (scop, pbbs); |
562 | isl_union_map *must_writes = scop_get_must_writes (scop, pbbs); | |
563 | isl_union_map *may_writes = scop_get_may_writes (scop, pbbs); | |
564 | isl_union_map *all_writes = isl_union_map_union | |
565 | (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes)); | |
566 | isl_space *space = isl_union_map_get_space (all_writes); | |
567 | isl_union_map *empty = isl_union_map_empty (space); | |
568 | isl_union_map *original = scop_get_original_schedule (scop, pbbs); | |
569 | int res; | |
570 | ||
571 | res = isl_union_map_compute_flow (isl_union_map_copy (reads), | |
572 | isl_union_map_copy (must_writes), | |
573 | isl_union_map_copy (may_writes), | |
574 | isl_union_map_copy (original), | |
575 | must_raw, may_raw, must_raw_no_source, | |
576 | may_raw_no_source); | |
577 | gcc_assert (res == 0); | |
578 | res = isl_union_map_compute_flow (isl_union_map_copy (all_writes), | |
579 | reads, empty, | |
580 | isl_union_map_copy (original), | |
581 | must_war, may_war, must_war_no_source, | |
582 | may_war_no_source); | |
583 | gcc_assert (res == 0); | |
584 | res = isl_union_map_compute_flow (all_writes, must_writes, may_writes, | |
585 | isl_union_map_copy (original), | |
586 | must_waw, may_waw, must_waw_no_source, | |
587 | may_waw_no_source); | |
588 | gcc_assert (res == 0); | |
589 | ||
590 | subtract_commutative_associative_deps | |
591 | (scop, pbbs, original, | |
592 | must_raw, may_raw, must_raw_no_source, may_raw_no_source, | |
593 | must_war, may_war, must_war_no_source, may_war_no_source, | |
594 | must_waw, may_waw, must_waw_no_source, may_waw_no_source); | |
de38f9c0 | 595 | } |
596 | ||
87e20041 | 597 | /* Given a TRANSFORM, check whether it respects the original |
598 | dependences in SCOP. Returns true when TRANSFORM is a safe | |
599 | transformation. */ | |
de38f9c0 | 600 | |
87e20041 | 601 | static bool |
602 | transform_is_safe (scop_p scop, isl_union_map *transform) | |
de38f9c0 | 603 | { |
87e20041 | 604 | bool res; |
605 | ||
606 | if (!scop->must_raw) | |
607 | compute_deps (scop, SCOP_BBS (scop), | |
608 | &scop->must_raw, &scop->may_raw, | |
609 | &scop->must_raw_no_source, &scop->may_raw_no_source, | |
610 | &scop->must_war, &scop->may_war, | |
611 | &scop->must_war_no_source, &scop->may_war_no_source, | |
612 | &scop->must_waw, &scop->may_waw, | |
613 | &scop->must_waw_no_source, &scop->may_waw_no_source); | |
614 | ||
615 | res = (no_violations (transform, scop->must_raw) | |
616 | && no_violations (transform, scop->may_raw) | |
617 | && no_violations (transform, scop->must_war) | |
618 | && no_violations (transform, scop->may_war) | |
619 | && no_violations (transform, scop->must_waw) | |
620 | && no_violations (transform, scop->may_waw)); | |
621 | ||
622 | isl_union_map_free (transform); | |
623 | return res; | |
de38f9c0 | 624 | } |
625 | ||
87e20041 | 626 | /* Return true when the SCOP transformed schedule is correct. */ |
de38f9c0 | 627 | |
87e20041 | 628 | bool |
629 | graphite_legal_transform (scop_p scop) | |
de38f9c0 | 630 | { |
87e20041 | 631 | int res; |
632 | isl_union_map *transform; | |
de38f9c0 | 633 | |
87e20041 | 634 | timevar_push (TV_GRAPHITE_DATA_DEPS); |
635 | transform = scop_get_transformed_schedule (scop, SCOP_BBS (scop)); | |
636 | res = transform_is_safe (scop, transform); | |
637 | timevar_pop (TV_GRAPHITE_DATA_DEPS); | |
96b6d5d7 | 638 | |
87e20041 | 639 | return res; |
96b6d5d7 | 640 | } |
641 | ||
429cca51 | 642 | #endif |