1 /* Data dependence analysis for Graphite. 2 Copyright (C) 2009, 2010, 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 #include "system.h" 24 #include "coretypes.h" 25 #include "tree-flow.h" 26 #include "tree-dump.h" 27 #include "cfgloop.h" 28 #include "tree-chrec.h" 29 #include "tree-data-ref.h" 30 #include "tree-scalar-evolution.h" 31 #include "sese.h" 32 33 #ifdef HAVE_cloog 34 #include "ppl_c.h" 35 #include "graphite-ppl.h" 36 #include "graphite-poly.h" 37 #include "graphite-dependences.h" 38 #include "graphite-cloog-util.h" 39 40 /* Comparison function for poly_ddr hash table. */ 41 42 int 43 eq_poly_ddr_p (const void *pddr1, const void *pddr2) 44 { 45 const struct poly_ddr *p1 = (const struct poly_ddr *) pddr1; 46 const struct poly_ddr *p2 = (const struct poly_ddr *) pddr2; 47 48 return (PDDR_SOURCE (p1) == PDDR_SOURCE (p2) 49 && PDDR_SINK (p1) == PDDR_SINK (p2)); 50 } 51 52 /* Hash function for poly_ddr hashtable. */ 53 54 hashval_t 55 hash_poly_ddr_p (const void *pddr) 56 { 57 const struct poly_ddr *p = (const struct poly_ddr *) pddr; 58 59 return (hashval_t) ((intptr_t) PDDR_SOURCE (p) + (intptr_t) PDDR_SINK (p)); 60 } 61 62 /* Returns true when PDDR has no dependence. */ 63 64 static bool 65 pddr_is_empty (poly_ddr_p pddr) 66 { 67 if (!pddr) 68 return true; 69 70 gcc_assert (PDDR_KIND (pddr) != unknown_dependence); 71 72 return PDDR_KIND (pddr) == no_dependence ? true : false; 73 } 74 75 /* Prints to FILE the layout of the dependence polyhedron of PDDR: 76 77 T1|I1|T2|I2|S1|S2|G 78 79 with 80 | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK 81 | I1 and I2 the iteration domains 82 | S1 and S2 the subscripts 83 | G the global parameters. */ 84 85 static void 86 print_dependence_polyhedron_layout (FILE *file, poly_ddr_p pddr) 87 { 88 poly_dr_p pdr1 = PDDR_SOURCE (pddr); 89 poly_dr_p pdr2 = PDDR_SINK (pddr); 90 poly_bb_p pbb1 = PDR_PBB (pdr1); 91 poly_bb_p pbb2 = PDR_PBB (pdr2); 92 93 graphite_dim_t i; 94 graphite_dim_t tdim1 = PDDR_ORIGINAL_SCATTERING_P (pddr) ? 95 pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1); 96 graphite_dim_t tdim2 = PDDR_ORIGINAL_SCATTERING_P (pddr) ? 97 pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2); 98 graphite_dim_t idim1 = pbb_dim_iter_domain (pbb1); 99 graphite_dim_t idim2 = pbb_dim_iter_domain (pbb2); 100 graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1; 101 graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1; 102 graphite_dim_t gdim = scop_nb_params (PBB_SCOP (pbb1)); 103 104 fprintf (file, "# eq"); 105 106 for (i = 0; i < tdim1; i++) 107 fprintf (file, " t1_%d", (int) i); 108 for (i = 0; i < idim1; i++) 109 fprintf (file, " i1_%d", (int) i); 110 for (i = 0; i < tdim2; i++) 111 fprintf (file, " t2_%d", (int) i); 112 for (i = 0; i < idim2; i++) 113 fprintf (file, " i2_%d", (int) i); 114 for (i = 0; i < sdim1; i++) 115 fprintf (file, " s1_%d", (int) i); 116 for (i = 0; i < sdim2; i++) 117 fprintf (file, " s2_%d", (int) i); 118 for (i = 0; i < gdim; i++) 119 fprintf (file, " g_%d", (int) i); 120 121 fprintf (file, " cst\n"); 122 } 123 124 /* Prints to FILE the poly_ddr_p PDDR. */ 125 126 void 127 print_pddr (FILE *file, poly_ddr_p pddr) 128 { 129 fprintf (file, "pddr (kind: "); 130 131 if (PDDR_KIND (pddr) == unknown_dependence) 132 fprintf (file, "unknown_dependence"); 133 else if (PDDR_KIND (pddr) == no_dependence) 134 fprintf (file, "no_dependence"); 135 else if (PDDR_KIND (pddr) == has_dependence) 136 fprintf (file, "has_dependence"); 137 138 fprintf (file, "\n source "); 139 print_pdr (file, PDDR_SOURCE (pddr), 2); 140 141 fprintf (file, "\n sink "); 142 print_pdr (file, PDDR_SINK (pddr), 2); 143 144 if (PDDR_KIND (pddr) == has_dependence) 145 { 146 fprintf (file, "\n dependence polyhedron (\n"); 147 print_dependence_polyhedron_layout (file, pddr); 148 ppl_print_powerset_matrix (file, PDDR_DDP (pddr)); 149 ppl_io_fprint_Pointset_Powerset_C_Polyhedron (file, PDDR_DDP (pddr)); 150 fprintf (file, ")\n"); 151 } 152 153 fprintf (file, ")\n"); 154 } 155 156 /* Prints to STDERR the poly_ddr_p PDDR. */ 157 158 DEBUG_FUNCTION void 159 debug_pddr (poly_ddr_p pddr) 160 { 161 print_pddr (stderr, pddr); 162 } 163 164 165 /* Remove all the dimensions except alias information at dimension 166 ALIAS_DIM. */ 167 168 static void 169 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset, 170 ppl_dimension_type alias_dim) 171 { 172 ppl_dimension_type *ds; 173 ppl_dimension_type access_dim; 174 unsigned i, pos; 175 176 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset, 177 &access_dim); 178 ds = XNEWVEC (ppl_dimension_type, access_dim - 1); 179 gcc_assert (alias_dim < access_dim); 180 181 for (pos = 0, i = 0; i < access_dim; i++) 182 if (i != alias_dim) 183 ds[pos++] = i; 184 185 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset, 186 ds, 187 access_dim - 1); 188 free (ds); 189 } 190 191 /* Return true when PDR1 and PDR2 may alias. */ 192 193 static bool 194 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2) 195 { 196 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2; 197 ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1); 198 ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2); 199 ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1); 200 ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2); 201 int empty_p; 202 203 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 204 (&alias_powerset1, accesses1); 205 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 206 (&alias_powerset2, accesses2); 207 208 build_alias_set_powerset (alias_powerset1, alias_dim1); 209 build_alias_set_powerset (alias_powerset2, alias_dim2); 210 211 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign 212 (alias_powerset1, alias_powerset2); 213 214 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1); 215 216 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1); 217 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2); 218 219 return !empty_p; 220 } 221 222 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is 223 transformed into "a CUT0 c CUT1' b" 224 225 Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b" 226 Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b" 227 Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b": 228 "00...0 a 00...0 c 00...0 b". */ 229 230 static ppl_Pointset_Powerset_C_Polyhedron_t 231 map_dr_into_dep_poly (graphite_dim_t dim, 232 ppl_Pointset_Powerset_C_Polyhedron_t dr, 233 graphite_dim_t cut0, graphite_dim_t cut1, 234 graphite_dim_t nb0, graphite_dim_t nb1) 235 { 236 ppl_dimension_type pdim; 237 ppl_dimension_type *map; 238 ppl_Pointset_Powerset_C_Polyhedron_t res; 239 ppl_dimension_type i; 240 241 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 242 (&res, dr); 243 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim); 244 245 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim); 246 247 /* First mapping: move 'g' vector to right position. */ 248 for (i = 0; i < cut0; i++) 249 map[i] = i; 250 251 for (i = cut0; i < cut1; i++) 252 map[i] = pdim - cut1 + i; 253 254 for (i = cut1; i < pdim; i++) 255 map[i] = cut0 + i - cut1; 256 257 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim); 258 free (map); 259 260 /* After swapping 's' and 'g' vectors, we have to update a new cut. */ 261 cut1 = pdim - cut1 + cut0; 262 263 ppl_insert_dimensions_pointset (res, 0, nb0); 264 ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1); 265 ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1, 266 dim - nb0 - nb1 - pdim); 267 268 return res; 269 } 270 271 /* Builds subscript equality constraints. */ 272 273 static ppl_Pointset_Powerset_C_Polyhedron_t 274 dr_equality_constraints (graphite_dim_t dim, 275 graphite_dim_t pos, graphite_dim_t nb_subscripts) 276 { 277 ppl_Polyhedron_t eqs; 278 ppl_Pointset_Powerset_C_Polyhedron_t res; 279 graphite_dim_t i; 280 281 ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0); 282 283 for (i = 0; i < nb_subscripts; i++) 284 { 285 ppl_Constraint_t cstr 286 = ppl_build_relation (dim, pos + i, pos + i + nb_subscripts, 287 0, PPL_CONSTRAINT_TYPE_EQUAL); 288 ppl_Polyhedron_add_constraint (eqs, cstr); 289 ppl_delete_Constraint (cstr); 290 } 291 292 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs); 293 ppl_delete_Polyhedron (eqs); 294 return res; 295 } 296 297 /* Builds scheduling inequality constraints: when DIRECTION is 298 1 builds a GE constraint, 299 0 builds an EQ constraint, 300 -1 builds a LE constraint. 301 DIM is the dimension of the scheduling space. 302 POS and POS + OFFSET are the dimensions that are related. */ 303 304 static ppl_Pointset_Powerset_C_Polyhedron_t 305 build_pairwise_scheduling (graphite_dim_t dim, 306 graphite_dim_t pos, 307 graphite_dim_t offset, 308 int direction) 309 { 310 ppl_Pointset_Powerset_C_Polyhedron_t res; 311 ppl_Polyhedron_t equalities; 312 ppl_Constraint_t cstr; 313 graphite_dim_t a = pos; 314 graphite_dim_t b = pos + offset; 315 316 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0); 317 318 switch (direction) 319 { 320 case 1: 321 /* Builds "a + 1 <= b. */ 322 cstr = ppl_build_relation (dim, a, b, 1, 323 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); 324 break; 325 326 case 0: 327 /* Builds "a = b. */ 328 cstr = ppl_build_relation (dim, a, b, 0, 329 PPL_CONSTRAINT_TYPE_EQUAL); 330 break; 331 332 case -1: 333 /* Builds "a >= b + 1. */ 334 cstr = ppl_build_relation (dim, a, b, -1, 335 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 336 break; 337 338 default: 339 gcc_unreachable (); 340 } 341 342 ppl_Polyhedron_add_constraint (equalities, cstr); 343 ppl_delete_Constraint (cstr); 344 345 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities); 346 ppl_delete_Polyhedron (equalities); 347 return res; 348 } 349 350 /* Add to a non empty polyhedron BAG the precedence constraints for 351 the lexicographical comparison of time vectors in BAG following the 352 lexicographical order. DIM is the dimension of the polyhedron BAG. 353 TDIM is the number of loops common to the two statements that are 354 compared lexicographically, i.e. the number of loops containing 355 both statements. OFFSET is the number of dimensions needed to 356 represent the first statement, i.e. dimT1 + dimI1 in the layout of 357 the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to 358 1, compute the direct dependence from PDR1 to PDR2, and when 359 DIRECTION is -1, compute the reversed dependence relation, from 360 PDR2 to PDR1. */ 361 362 static ppl_Pointset_Powerset_C_Polyhedron_t 363 build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag, 364 graphite_dim_t dim, 365 graphite_dim_t tdim, 366 graphite_dim_t offset, 367 int direction) 368 { 369 graphite_dim_t i; 370 ppl_Pointset_Powerset_C_Polyhedron_t res, lex; 371 372 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1); 373 374 lex = build_pairwise_scheduling (dim, 0, offset, direction); 375 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); 376 377 if (!ppl_powerset_is_empty (lex)) 378 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); 379 380 ppl_delete_Pointset_Powerset_C_Polyhedron (lex); 381 382 for (i = 0; i < tdim - 1; i++) 383 { 384 ppl_Pointset_Powerset_C_Polyhedron_t sceq; 385 386 sceq = build_pairwise_scheduling (dim, i, offset, 0); 387 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq); 388 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq); 389 390 if (ppl_powerset_is_empty (bag)) 391 break; 392 393 lex = build_pairwise_scheduling (dim, i + 1, offset, direction); 394 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); 395 396 if (!ppl_powerset_is_empty (lex)) 397 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); 398 399 ppl_delete_Pointset_Powerset_C_Polyhedron (lex); 400 } 401 402 return res; 403 } 404 405 /* Build the dependence polyhedron for data references PDR1 and PDR2. 406 The layout of the dependence polyhedron is: 407 408 T1|I1|T2|I2|S1|S2|G 409 410 with 411 | T1 and T2 the scattering dimensions for PDR1 and PDR2 412 | I1 and I2 the iteration domains 413 | S1 and S2 the subscripts 414 | G the global parameters. 415 416 When DIRECTION is set to 1, compute the direct dependence from PDR1 417 to PDR2, and when DIRECTION is -1, compute the reversed dependence 418 relation, from PDR2 to PDR1. */ 419 420 static ppl_Pointset_Powerset_C_Polyhedron_t 421 dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2, 422 int direction, bool original_scattering_p) 423 { 424 poly_bb_p pbb1 = PDR_PBB (pdr1); 425 poly_bb_p pbb2 = PDR_PBB (pdr2); 426 scop_p scop = PBB_SCOP (pbb1); 427 graphite_dim_t tdim1 = original_scattering_p ? 428 pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1); 429 graphite_dim_t tdim2 = original_scattering_p ? 430 pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2); 431 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1); 432 graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2); 433 graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1; 434 graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1; 435 graphite_dim_t gdim = scop_nb_params (scop); 436 graphite_dim_t dim1 = pdr_dim (pdr1); 437 graphite_dim_t dim2 = pdr_dim (pdr2); 438 graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim; 439 ppl_Pointset_Powerset_C_Polyhedron_t res; 440 ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2; 441 ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq; 442 ppl_Pointset_Powerset_C_Polyhedron_t lex; 443 444 gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2)); 445 446 combine_context_id_scat (&sc1, pbb1, original_scattering_p); 447 combine_context_id_scat (&sc2, pbb2, original_scattering_p); 448 449 ppl_insert_dimensions_pointset (sc1, tdim1 + ddim1, 450 tdim2 + ddim2 + sdim1 + sdim2); 451 452 ppl_insert_dimensions_pointset (sc2, 0, tdim1 + ddim1); 453 ppl_insert_dimensions_pointset (sc2, tdim1 + ddim1 + tdim2 + ddim2, 454 sdim1 + sdim2); 455 456 idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim, 457 tdim1, tdim2 + ddim2); 458 idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim, 459 tdim1 + ddim1 + tdim2, sdim1); 460 461 /* Now add the subscript equalities. */ 462 dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1); 463 464 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0); 465 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc1); 466 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc2); 467 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1); 468 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2); 469 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq); 470 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1); 471 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2); 472 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1); 473 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2); 474 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq); 475 476 if (ppl_powerset_is_empty (res)) 477 return NULL; 478 479 lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2), 480 tdim1 + ddim1, direction); 481 ppl_delete_Pointset_Powerset_C_Polyhedron (res); 482 483 return lex; 484 } 485 486 /* Build the dependence polyhedron for data references PDR1 and PDR2. 487 If possible use already cached information. 488 489 When DIRECTION is set to 1, compute the direct dependence from PDR1 490 to PDR2, and when DIRECTION is -1, compute the reversed dependence 491 relation, from PDR2 to PDR1. */ 492 493 static poly_ddr_p 494 new_poly_ddr (poly_dr_p pdr1, poly_dr_p pdr2, 495 int direction, bool original_scattering_p) 496 { 497 PTR *x = NULL; 498 poly_ddr_p res; 499 bool may_alias; 500 501 /* Return the PDDR from the cache if it already has been computed. */ 502 if (original_scattering_p) 503 { 504 struct poly_ddr tmp; 505 scop_p scop = PBB_SCOP (PDR_PBB (pdr1)); 506 507 tmp.source = pdr1; 508 tmp.sink = pdr2; 509 x = htab_find_slot (SCOP_ORIGINAL_PDDRS (scop), 510 &tmp, INSERT); 511 512 if (x && *x) 513 return (poly_ddr_p) *x; 514 } 515 516 res = XNEW (struct poly_ddr); 517 PDDR_SOURCE (res) = pdr1; 518 PDDR_SINK (res) = pdr2; 519 PDDR_DDP (res) = NULL; 520 PDDR_ORIGINAL_SCATTERING_P (res) = original_scattering_p; 521 PDDR_KIND (res) = unknown_dependence; 522 523 may_alias = poly_drs_may_alias_p (pdr1, pdr2); 524 525 if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) 526 && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) 527 && may_alias) 528 PDDR_KIND (res) = unknown_dependence; 529 530 else if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) 531 && same_pdr_p (pdr1, pdr2) 532 && may_alias) 533 { 534 PDDR_DDP (res) = dependence_polyhedron (pdr1, pdr2, direction, 535 original_scattering_p); 536 if (PDDR_DDP (res)) 537 PDDR_KIND (res) = has_dependence; 538 else 539 PDDR_KIND (res) = no_dependence; 540 } 541 else 542 PDDR_KIND (res) = no_dependence; 543 544 if (original_scattering_p) 545 *x = res; 546 547 return res; 548 } 549 550 /* Free the data dependence relation poly_ddr_p P. */ 551 552 void 553 free_poly_ddr (void *p) 554 { 555 poly_ddr_p pddr = (poly_ddr_p) p; 556 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr)); 557 free (pddr); 558 } 559 560 /* Return true when the data dependence relation between the data 561 references PDR1 belonging to PBB1 and PDR2 is part of a 562 reduction. */ 563 564 static inline bool 565 reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2) 566 { 567 int i; 568 poly_dr_p pdr; 569 570 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr) 571 if (PDR_TYPE (pdr) == PDR_WRITE 572 && same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2)) 573 return true; 574 575 return false; 576 } 577 578 /* Return true when the data dependence relation between the data 579 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is 580 part of a reduction. */ 581 582 static inline bool 583 reduction_dr_p (poly_dr_p pdr1, poly_dr_p pdr2) 584 { 585 poly_bb_p pbb1 = PDR_PBB (pdr1); 586 poly_bb_p pbb2 = PDR_PBB (pdr2); 587 588 if (PBB_IS_REDUCTION (pbb1)) 589 return reduction_dr_1 (pbb1, pdr1, pdr2); 590 591 if (PBB_IS_REDUCTION (pbb2)) 592 return reduction_dr_1 (pbb2, pdr2, pdr1); 593 594 return false; 595 } 596 597 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1 598 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING 599 functions. */ 600 601 static bool 602 graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2) 603 { 604 ppl_Pointset_Powerset_C_Polyhedron_t po, pt; 605 graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2; 606 ppl_Pointset_Powerset_C_Polyhedron_t po_temp; 607 ppl_dimension_type pdim; 608 bool is_empty_p; 609 poly_ddr_p opddr, tpddr; 610 poly_bb_p pbb1, pbb2; 611 612 if (reduction_dr_p (pdr1, pdr2)) 613 return true; 614 615 /* We build the reverse dependence relation for the transformed 616 scattering, such that when we intersect it with the original PO, 617 we get an empty intersection when the transform is legal: 618 i.e. the transform should reverse no dependences, and so PT, the 619 reversed transformed PDDR, should have no constraint from PO. */ 620 opddr = new_poly_ddr (pdr1, pdr2, 1, true); 621 622 if (PDDR_KIND (opddr) == unknown_dependence) 623 return false; 624 625 /* There are no dependences between PDR1 and PDR2 in the original 626 version of the program, or after the transform, so the 627 transform is legal. */ 628 if (pddr_is_empty (opddr)) 629 return true; 630 631 tpddr = new_poly_ddr (pdr1, pdr2, -1, false); 632 633 if (PDDR_KIND (tpddr) == unknown_dependence) 634 { 635 free_poly_ddr (tpddr); 636 return false; 637 } 638 639 if (pddr_is_empty (tpddr)) 640 { 641 free_poly_ddr (tpddr); 642 return true; 643 } 644 645 po = PDDR_DDP (opddr); 646 pt = PDDR_DDP (tpddr); 647 648 /* Copy PO into PO_TEMP, such that PO is not destroyed. PO is 649 stored in a cache and should not be modified or freed. */ 650 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim); 651 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp, 652 pdim, 0); 653 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, po); 654 655 /* Extend PO and PT to have the same dimensions. */ 656 pbb1 = PDR_PBB (pdr1); 657 pbb2 = PDR_PBB (pdr2); 658 ddim1 = pbb_dim_iter_domain (pbb1); 659 otdim1 = pbb_nb_scattering_orig (pbb1); 660 otdim2 = pbb_nb_scattering_orig (pbb2); 661 ttdim1 = pbb_nb_scattering_transform (pbb1); 662 ttdim2 = pbb_nb_scattering_transform (pbb2); 663 ppl_insert_dimensions_pointset (po_temp, otdim1, ttdim1); 664 ppl_insert_dimensions_pointset (po_temp, otdim1 + ttdim1 + ddim1 + otdim2, 665 ttdim2); 666 ppl_insert_dimensions_pointset (pt, 0, otdim1); 667 ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2); 668 669 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt); 670 is_empty_p = ppl_powerset_is_empty (po_temp); 671 672 ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp); 673 free_poly_ddr (tpddr); 674 675 if (dump_file && (dump_flags & TDF_DETAILS)) 676 fprintf (dump_file, "\nloop carries dependency.\n"); 677 678 return is_empty_p; 679 } 680 681 /* Return true when the data dependence relation for PBB1 and PBB2 is 682 part of a reduction. */ 683 684 static inline bool 685 reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2) 686 { 687 return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1); 688 } 689 690 /* Iterates over the data references of PBB1 and PBB2 and detect 691 whether the transformed schedule is correct. */ 692 693 static bool 694 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2) 695 { 696 int i, j; 697 poly_dr_p pdr1, pdr2; 698 699 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1)) 700 pbb_remove_duplicate_pdrs (pbb1); 701 702 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2)) 703 pbb_remove_duplicate_pdrs (pbb2); 704 705 if (reduction_ddr_p (pbb1, pbb2)) 706 return true; 707 708 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) 709 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) 710 if (!graphite_legal_transform_dr (pdr1, pdr2)) 711 return false; 712 713 return true; 714 } 715 716 /* Iterates over the SCOP and detect whether the transformed schedule 717 is correct. */ 718 719 bool 720 graphite_legal_transform (scop_p scop) 721 { 722 int i, j; 723 poly_bb_p pbb1, pbb2; 724 725 timevar_push (TV_GRAPHITE_DATA_DEPS); 726 727 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) 728 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) 729 if (!graphite_legal_transform_bb (pbb1, pbb2)) 730 { 731 timevar_pop (TV_GRAPHITE_DATA_DEPS); 732 return false; 733 } 734 735 timevar_pop (TV_GRAPHITE_DATA_DEPS); 736 return true; 737 } 738 739 /* Returns TRUE when the dependence polyhedron between PDR1 and 740 PDR2 represents a loop carried dependence at level LEVEL. */ 741 742 static bool 743 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2, 744 int level) 745 { 746 ppl_Pointset_Powerset_C_Polyhedron_t po; 747 ppl_Pointset_Powerset_C_Polyhedron_t eqpp; 748 poly_bb_p pbb = PDR_PBB (pdr1); 749 graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb); 750 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb); 751 ppl_dimension_type dim; 752 bool empty_p; 753 poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, false); 754 graphite_dim_t pos; 755 756 if (PDDR_KIND (pddr) == unknown_dependence) 757 { 758 free_poly_ddr (pddr); 759 return true; 760 } 761 762 if (pddr_is_empty (pddr)) 763 { 764 free_poly_ddr (pddr); 765 return false; 766 } 767 768 po = PDDR_DDP (pddr); 769 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim); 770 pos = psct_dynamic_dim (pbb, level); 771 eqpp = build_pairwise_scheduling (dim, pos, tdim1 + ddim1, 1); 772 773 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po); 774 empty_p = ppl_powerset_is_empty (eqpp); 775 776 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp); 777 free_poly_ddr (pddr); 778 779 return !empty_p; 780 } 781 782 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */ 783 784 bool 785 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level) 786 { 787 int i, j; 788 poly_dr_p pdr1, pdr2; 789 790 timevar_push (TV_GRAPHITE_DATA_DEPS); 791 792 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) 793 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) 794 if (graphite_carried_dependence_level_k (pdr1, pdr2, level)) 795 { 796 timevar_pop (TV_GRAPHITE_DATA_DEPS); 797 return true; 798 } 799 800 timevar_pop (TV_GRAPHITE_DATA_DEPS); 801 return false; 802 } 803 804 /* When ORIG is true, pretty print to FILE all the original data 805 dependences of SCoP in DOT format, otherwise print the transformed 806 data deps. */ 807 808 static void 809 dot_deps_stmt_2 (FILE *file, scop_p scop, bool orig) 810 { 811 int i, j, k, l; 812 poly_bb_p pbb1, pbb2; 813 poly_dr_p pdr1, pdr2; 814 815 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) 816 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) 817 { 818 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) 819 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) 820 { 821 poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig); 822 823 if (!pddr_is_empty (pddr)) 824 { 825 fprintf (file, orig ? "OS%d -> OS%d\n" : "TS%d -> TS%d\n", 826 pbb_index (pbb1), pbb_index (pbb2)); 827 828 free_poly_ddr (pddr); 829 goto done; 830 } 831 832 free_poly_ddr (pddr); 833 } 834 done:; 835 } 836 } 837 838 /* Pretty print to FILE all the data dependences of SCoP in DOT 839 format. */ 840 841 static void 842 dot_deps_stmt_1 (FILE *file, scop_p scop) 843 { 844 fputs ("digraph all {\n", file); 845 846 dot_deps_stmt_2 (file, scop, true); 847 dot_deps_stmt_2 (file, scop, false); 848 849 fputs ("}\n\n", file); 850 } 851 852 /* When ORIG is true, pretty print to FILE all the original data 853 dependences of SCoP in DOT format, otherwise print the transformed 854 data deps. */ 855 856 static void 857 dot_deps_2 (FILE *file, scop_p scop, bool orig) 858 { 859 int i, j, k, l; 860 poly_bb_p pbb1, pbb2; 861 poly_dr_p pdr1, pdr2; 862 863 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) 864 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) 865 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) 866 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) 867 { 868 poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig); 869 870 if (!pddr_is_empty (pddr)) 871 fprintf (file, orig 872 ? "OS%d_D%d -> OS%d_D%d\n" : "TS%d_D%d -> TS%d_D%d\n", 873 pbb_index (pbb1), PDR_ID (pdr1), 874 pbb_index (pbb2), PDR_ID (pdr2)); 875 876 free_poly_ddr (pddr); 877 } 878 } 879 880 /* Pretty print to FILE all the data dependences of SCoP in DOT 881 format. */ 882 883 static void 884 dot_deps_1 (FILE *file, scop_p scop) 885 { 886 fputs ("digraph all {\n", file); 887 888 dot_deps_2 (file, scop, true); 889 dot_deps_2 (file, scop, false); 890 891 fputs ("}\n\n", file); 892 } 893 894 /* Display all the data dependences in SCoP using dotty. */ 895 896 DEBUG_FUNCTION void 897 dot_deps (scop_p scop) 898 { 899 /* When debugging, enable the following code. This cannot be used 900 in production compilers because it calls "system". */ 901 #if 0 902 FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); 903 gcc_assert (stream); 904 905 dot_deps_1 (stream, scop); 906 fclose (stream); 907 908 system ("dotty /tmp/scopdeps.dot &"); 909 #else 910 dot_deps_1 (stderr, scop); 911 #endif 912 } 913 914 /* Display all the statement dependences in SCoP using dotty. */ 915 916 DEBUG_FUNCTION void 917 dot_deps_stmt (scop_p scop) 918 { 919 /* When debugging, enable the following code. This cannot be used 920 in production compilers because it calls "system". */ 921 #if 0 922 FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); 923 gcc_assert (stream); 924 925 dot_deps_stmt_1 (stream, scop); 926 fclose (stream); 927 928 system ("dotty /tmp/scopdeps.dot &"); 929 #else 930 dot_deps_stmt_1 (stderr, scop); 931 #endif 932 } 933 934 #endif 935