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