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