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