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