gcc/graphite-dependences.c

   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 "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) ((long) PDDR_SOURCE (p) + (long) 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 = 0;
 175
 176   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
 177                                                       &access_dim);
 178   ds = XNEWVEC (ppl_dimension_type, access_dim-1);
 179   for (i = 0; i < access_dim; i++)
 180     {
 181       if (i == alias_dim)
 182         continue;
 183
 184       ds[pos] = i;
 185       pos++;
 186     }
 187
 188   ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
 189                                                               ds,
 190                                                               access_dim - 1);
 191   free (ds);
 192 }
 193
 194 /* Return true when PDR1 and PDR2 may alias.  */
 195
 196 static bool
 197 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
 198 {
 199   ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
 200   ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
 201   ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
 202   ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
 203   ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
 204   int empty_p;
 205
 206   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 207     (&alias_powerset1, accesses1);
 208   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 209     (&alias_powerset2, accesses2);
 210
 211   build_alias_set_powerset (alias_powerset1, alias_dim1);
 212   build_alias_set_powerset (alias_powerset2, alias_dim2);
 213
 214   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
 215     (alias_powerset1, alias_powerset2);
 216
 217   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
 218
 219   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
 220   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
 221
 222   return !empty_p;
 223 }
 224
 225 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
 226    transformed into "a CUT0 c CUT1' b"
 227
 228    Add NB0 zeros before "a":  "00...0 a CUT0 c CUT1' b"
 229    Add NB1 zeros between "a" and "c":  "00...0 a 00...0 c CUT1' b"
 230    Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
 231    "00...0 a 00...0 c 00...0 b".  */
 232
 233 static ppl_Pointset_Powerset_C_Polyhedron_t
 234 map_dr_into_dep_poly (graphite_dim_t dim,
 235                       ppl_Pointset_Powerset_C_Polyhedron_t dr,
 236                       graphite_dim_t cut0, graphite_dim_t cut1,
 237                       graphite_dim_t nb0, graphite_dim_t nb1)
 238 {
 239   ppl_dimension_type pdim;
 240   ppl_dimension_type *map;
 241   ppl_Pointset_Powerset_C_Polyhedron_t res;
 242   ppl_dimension_type i;
 243
 244   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 245     (&res, dr);
 246   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim);
 247
 248   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim);
 249
 250   /* First mapping: move 'g' vector to right position.  */
 251   for (i = 0; i < cut0; i++)
 252     map[i] = i;
 253
 254   for (i = cut0; i < cut1; i++)
 255     map[i] = pdim - cut1 + i;
 256
 257   for (i = cut1; i < pdim; i++)
 258     map[i] = cut0 + i - cut1;
 259
 260   ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim);
 261   free (map);
 262
 263   /* After swapping 's' and 'g' vectors, we have to update a new cut.  */
 264   cut1 = pdim - cut1 + cut0;
 265
 266   ppl_insert_dimensions_pointset (res, 0, nb0);
 267   ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1);
 268   ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1,
 269                                   dim - nb0 - nb1 - pdim);
 270
 271   return res;
 272 }
 273
 274 /* Builds subscript equality constraints.  */
 275
 276 static ppl_Pointset_Powerset_C_Polyhedron_t
 277 dr_equality_constraints (graphite_dim_t dim,
 278                          graphite_dim_t pos, graphite_dim_t nb_subscripts)
 279 {
 280   ppl_Polyhedron_t eqs;
 281   ppl_Pointset_Powerset_C_Polyhedron_t res;
 282   graphite_dim_t i;
 283
 284   ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0);
 285
 286   for (i = 0; i < nb_subscripts; i++)
 287     {
 288       ppl_Constraint_t cstr
 289         = ppl_build_relation (dim, pos + i, pos + i + nb_subscripts,
 290                               0, PPL_CONSTRAINT_TYPE_EQUAL);
 291       ppl_Polyhedron_add_constraint (eqs, cstr);
 292       ppl_delete_Constraint (cstr);
 293     }
 294
 295   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs);
 296   ppl_delete_Polyhedron (eqs);
 297   return res;
 298 }
 299
 300 /* Builds scheduling inequality constraints: when DIRECTION is
 301    1 builds a GE constraint,
 302    0 builds an EQ constraint,
 303    -1 builds a LE constraint.
 304    DIM is the dimension of the scheduling space.
 305    POS and POS + OFFSET are the dimensions that are related.  */
 306
 307 static ppl_Pointset_Powerset_C_Polyhedron_t
 308 build_pairwise_scheduling (graphite_dim_t dim,
 309                            graphite_dim_t pos,
 310                            graphite_dim_t offset,
 311                            int direction)
 312 {
 313   ppl_Pointset_Powerset_C_Polyhedron_t res;
 314   ppl_Polyhedron_t equalities;
 315   ppl_Constraint_t cstr;
 316   graphite_dim_t a = pos;
 317   graphite_dim_t b = pos + offset;
 318
 319   ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
 320
 321   switch (direction)
 322     {
 323     case 1:
 324       /* Builds "a + 1 <= b.  */
 325       cstr = ppl_build_relation (dim, a, b, 1,
 326                                  PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
 327       break;
 328
 329     case 0:
 330       /* Builds "a = b.  */
 331       cstr = ppl_build_relation (dim, a, b, 0,
 332                                  PPL_CONSTRAINT_TYPE_EQUAL);
 333       break;
 334
 335     case -1:
 336       /* Builds "a >= b + 1.  */
 337       cstr = ppl_build_relation (dim, a, b, -1,
 338                                  PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 339       break;
 340
 341     default:
 342       gcc_unreachable ();
 343     }
 344
 345   ppl_Polyhedron_add_constraint (equalities, cstr);
 346   ppl_delete_Constraint (cstr);
 347
 348   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
 349   ppl_delete_Polyhedron (equalities);
 350   return res;
 351 }
 352
 353 /* Add to a non empty polyhedron BAG the precedence constraints for
 354    the lexicographical comparison of time vectors in BAG following the
 355    lexicographical order.  DIM is the dimension of the polyhedron BAG.
 356    TDIM is the number of loops common to the two statements that are
 357    compared lexicographically, i.e. the number of loops containing
 358    both statements.  OFFSET is the number of dimensions needed to
 359    represent the first statement, i.e. dimT1 + dimI1 in the layout of
 360    the BAG polyhedron: T1|I1|T2|I2|S1|S2|G.  When DIRECTION is set to
 361    1, compute the direct dependence from PDR1 to PDR2, and when
 362    DIRECTION is -1, compute the reversed dependence relation, from
 363    PDR2 to PDR1.  */
 364
 365 static ppl_Pointset_Powerset_C_Polyhedron_t
 366 build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
 367                                   graphite_dim_t dim,
 368                                   graphite_dim_t tdim,
 369                                   graphite_dim_t offset,
 370                                   int direction)
 371 {
 372   graphite_dim_t i;
 373   ppl_Pointset_Powerset_C_Polyhedron_t res, lex;
 374
 375   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1);
 376
 377   lex = build_pairwise_scheduling (dim, 0, offset, direction);
 378   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
 379
 380   if (!ppl_powerset_is_empty (lex))
 381     ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
 382
 383   ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
 384
 385   for (i = 0; i < tdim - 1; i++)
 386     {
 387       ppl_Pointset_Powerset_C_Polyhedron_t sceq;
 388
 389       sceq = build_pairwise_scheduling (dim, i, offset, 0);
 390       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
 391       ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
 392
 393       if (ppl_powerset_is_empty (bag))
 394         break;
 395
 396       lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
 397       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
 398
 399       if (!ppl_powerset_is_empty (lex))
 400         ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
 401
 402       ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
 403     }
 404
 405   return res;
 406 }
 407
 408 /* Build the dependence polyhedron for data references PDR1 and PDR2.
 409    The layout of the dependence polyhedron is:
 410
 411    T1|I1|T2|I2|S1|S2|G
 412
 413    with
 414    | T1 and T2 the scattering dimensions for PDR1 and PDR2
 415    | I1 and I2 the iteration domains
 416    | S1 and S2 the subscripts
 417    | G the global parameters.
 418
 419    When DIRECTION is set to 1, compute the direct dependence from PDR1
 420    to PDR2, and when DIRECTION is -1, compute the reversed dependence
 421    relation, from PDR2 to PDR1.  */
 422
 423 static ppl_Pointset_Powerset_C_Polyhedron_t
 424 dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
 425                        int direction, bool original_scattering_p)
 426 {
 427   poly_bb_p pbb1 = PDR_PBB (pdr1);
 428   poly_bb_p pbb2 = PDR_PBB (pdr2);
 429   scop_p scop = PBB_SCOP (pbb1);
 430   graphite_dim_t tdim1 = original_scattering_p ?
 431     pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
 432   graphite_dim_t tdim2 = original_scattering_p ?
 433     pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
 434   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 435   graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
 436   graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
 437   graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
 438   graphite_dim_t gdim = scop_nb_params (scop);
 439   graphite_dim_t dim1 = pdr_dim (pdr1);
 440   graphite_dim_t dim2 = pdr_dim (pdr2);
 441   graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim;
 442   ppl_Pointset_Powerset_C_Polyhedron_t res;
 443   ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2;
 444   ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
 445   ppl_Pointset_Powerset_C_Polyhedron_t lex;
 446
 447   gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
 448
 449   combine_context_id_scat (&sc1, pbb1, original_scattering_p);
 450   combine_context_id_scat (&sc2, pbb2, original_scattering_p);
 451
 452   ppl_insert_dimensions_pointset (sc1, tdim1 + ddim1,
 453                                   tdim2 + ddim2 + sdim1 + sdim2);
 454
 455   ppl_insert_dimensions_pointset (sc2, 0, tdim1 + ddim1);
 456   ppl_insert_dimensions_pointset (sc2, tdim1 + ddim1 + tdim2 + ddim2,
 457                                   sdim1 + sdim2);
 458
 459   idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
 460                                tdim1, tdim2 + ddim2);
 461   idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
 462                                tdim1 + ddim1 + tdim2, sdim1);
 463
 464   /* Now add the subscript equalities.  */
 465   dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
 466
 467   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
 468   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc1);
 469   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc2);
 470   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1);
 471   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
 472   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq);
 473   ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
 474   ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
 475   ppl_delete_Pointset_Powerset_C_Polyhedron (idr1);
 476   ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
 477   ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
 478
 479   if (ppl_powerset_is_empty (res))
 480     return NULL;
 481
 482   lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
 483                                           tdim1 + ddim1, direction);
 484   ppl_delete_Pointset_Powerset_C_Polyhedron (res);
 485
 486   return lex;
 487 }
 488
 489 /* Build the dependence polyhedron for data references PDR1 and PDR2.
 490    If possible use already cached information.
 491
 492    When DIRECTION is set to 1, compute the direct dependence from PDR1
 493    to PDR2, and when DIRECTION is -1, compute the reversed dependence
 494    relation, from PDR2 to PDR1.  */
 495
 496 static poly_ddr_p
 497 new_poly_ddr (poly_dr_p pdr1, poly_dr_p pdr2,
 498               int direction, bool original_scattering_p)
 499 {
 500   PTR *x = NULL;
 501   poly_ddr_p res;
 502   bool may_alias;
 503
 504   /* Return the PDDR from the cache if it already has been computed.  */
 505   if (original_scattering_p)
 506     {
 507       struct poly_ddr tmp;
 508       scop_p scop = PBB_SCOP (PDR_PBB (pdr1));
 509
 510       tmp.source = pdr1;
 511       tmp.sink = pdr2;
 512       x = htab_find_slot (SCOP_ORIGINAL_PDDRS (scop),
 513                           &tmp, INSERT);
 514
 515       if (x && *x)
 516         return (poly_ddr_p) *x;
 517     }
 518
 519   res = XNEW (struct poly_ddr);
 520   PDDR_SOURCE (res) = pdr1;
 521   PDDR_SINK (res) = pdr2;
 522   PDDR_DDP (res) = NULL;
 523   PDDR_ORIGINAL_SCATTERING_P (res) = original_scattering_p;
 524   PDDR_KIND (res) = unknown_dependence;
 525
 526   may_alias = poly_drs_may_alias_p (pdr1, pdr2);
 527
 528   if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
 529       && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
 530       && may_alias)
 531     PDDR_KIND (res) = unknown_dependence;
 532
 533   else if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
 534            && same_pdr_p (pdr1, pdr2)
 535            && may_alias)
 536     {
 537       PDDR_DDP (res) = dependence_polyhedron (pdr1, pdr2, direction,
 538                                               original_scattering_p);
 539       if (PDDR_DDP (res))
 540         PDDR_KIND (res) = has_dependence;
 541       else
 542         PDDR_KIND (res) = no_dependence;
 543     }
 544   else
 545     PDDR_KIND (res) = no_dependence;
 546
 547   if (original_scattering_p)
 548     *x = res;
 549
 550   return res;
 551 }
 552
 553 /* Free the data dependence relation poly_ddr_p P.  */
 554
 555 void
 556 free_poly_ddr (void *p)
 557 {
 558   poly_ddr_p pddr = (poly_ddr_p) p;
 559   ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
 560   free (pddr);
 561 }
 562
 563 /* Return true when the data dependence relation between the data
 564    references PDR1 belonging to PBB1 and PDR2 is part of a
 565    reduction.  */
 566
 567 static inline bool
 568 reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
 569 {
 570   int i;
 571   poly_dr_p pdr;
 572
 573   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr)
 574     if (PDR_TYPE (pdr) == PDR_WRITE
 575         && same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2))
 576       return true;
 577
 578   return false;
 579 }
 580
 581 /* Return true when the data dependence relation between the data
 582    references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
 583    part of a reduction.  */
 584
 585 static inline bool
 586 reduction_dr_p (poly_dr_p pdr1, poly_dr_p pdr2)
 587 {
 588   poly_bb_p pbb1 = PDR_PBB (pdr1);
 589   poly_bb_p pbb2 = PDR_PBB (pdr2);
 590
 591   if (PBB_IS_REDUCTION (pbb1))
 592     return reduction_dr_1 (pbb1, pdr1, pdr2);
 593
 594   if (PBB_IS_REDUCTION (pbb2))
 595     return reduction_dr_1 (pbb2, pdr2, pdr1);
 596
 597   return false;
 598 }
 599
 600 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
 601    and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
 602    functions.  */
 603
 604 static bool
 605 graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
 606 {
 607   ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
 608   graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
 609   ppl_Pointset_Powerset_C_Polyhedron_t po_temp;
 610   ppl_dimension_type pdim;
 611   bool is_empty_p;
 612   poly_ddr_p opddr, tpddr;
 613   poly_bb_p pbb1, pbb2;
 614
 615   if (reduction_dr_p (pdr1, pdr2))
 616     return true;
 617
 618   /* We build the reverse dependence relation for the transformed
 619      scattering, such that when we intersect it with the original PO,
 620      we get an empty intersection when the transform is legal:
 621      i.e. the transform should reverse no dependences, and so PT, the
 622      reversed transformed PDDR, should have no constraint from PO.  */
 623   opddr = new_poly_ddr (pdr1, pdr2, 1, true);
 624
 625   if (PDDR_KIND (opddr) == unknown_dependence)
 626     return false;
 627
 628     /* There are no dependences between PDR1 and PDR2 in the original
 629        version of the program, or after the transform, so the
 630        transform is legal.  */
 631   if (pddr_is_empty (opddr))
 632     return true;
 633
 634   tpddr = new_poly_ddr (pdr1, pdr2, -1, false);
 635
 636   if (PDDR_KIND (tpddr) == unknown_dependence)
 637     {
 638       free_poly_ddr (tpddr);
 639       return false;
 640     }
 641
 642   if (pddr_is_empty (tpddr))
 643     {
 644       free_poly_ddr (tpddr);
 645       return true;
 646     }
 647
 648   po = PDDR_DDP (opddr);
 649   pt = PDDR_DDP (tpddr);
 650
 651   /* Copy PO into PO_TEMP, such that PO is not destroyed.  PO is
 652      stored in a cache and should not be modified or freed.  */
 653   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
 654   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp,
 655                                                                pdim, 0);
 656   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, po);
 657
 658   /* Extend PO and PT to have the same dimensions.  */
 659   pbb1 = PDR_PBB (pdr1);
 660   pbb2 = PDR_PBB (pdr2);
 661   ddim1 = pbb_dim_iter_domain (pbb1);
 662   otdim1 = pbb_nb_scattering_orig (pbb1);
 663   otdim2 = pbb_nb_scattering_orig (pbb2);
 664   ttdim1 = pbb_nb_scattering_transform (pbb1);
 665   ttdim2 = pbb_nb_scattering_transform (pbb2);
 666   ppl_insert_dimensions_pointset (po_temp, otdim1, ttdim1);
 667   ppl_insert_dimensions_pointset (po_temp, otdim1 + ttdim1 + ddim1 + otdim2,
 668                                   ttdim2);
 669   ppl_insert_dimensions_pointset (pt, 0, otdim1);
 670   ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
 671
 672   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
 673   is_empty_p = ppl_powerset_is_empty (po_temp);
 674
 675   ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
 676   free_poly_ddr (tpddr);
 677
 678   if (dump_file && (dump_flags & TDF_DETAILS))
 679     fprintf (dump_file, "\nloop carries dependency.\n");
 680
 681   return is_empty_p;
 682 }
 683
 684 /* Return true when the data dependence relation for PBB1 and PBB2 is
 685    part of a reduction.  */
 686
 687 static inline bool
 688 reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
 689 {
 690   return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
 691 }
 692
 693 /* Iterates over the data references of PBB1 and PBB2 and detect
 694    whether the transformed schedule is correct.  */
 695
 696 static bool
 697 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
 698 {
 699   int i, j;
 700   poly_dr_p pdr1, pdr2;
 701
 702   if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
 703     pbb_remove_duplicate_pdrs (pbb1);
 704
 705   if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
 706     pbb_remove_duplicate_pdrs (pbb2);
 707
 708   if (reduction_ddr_p (pbb1, pbb2))
 709     return true;
 710
 711   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1)
 712     FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2)
 713       if (!graphite_legal_transform_dr (pdr1, pdr2))
 714         return false;
 715
 716   return true;
 717 }
 718
 719 /* Iterates over the SCOP and detect whether the transformed schedule
 720    is correct.  */
 721
 722 bool
 723 graphite_legal_transform (scop_p scop)
 724 {
 725   int i, j;
 726   poly_bb_p pbb1, pbb2;
 727
 728   timevar_push (TV_GRAPHITE_DATA_DEPS);
 729
 730   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
 731     FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
 732       if (!graphite_legal_transform_bb (pbb1, pbb2))
 733         {
 734           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 735           return false;
 736         }
 737
 738   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 739   return true;
 740 }
 741
 742 /* Returns TRUE when the dependence polyhedron between PDR1 and
 743    PDR2 represents a loop carried dependence at level LEVEL.  */
 744
 745 static bool
 746 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
 747                                      int level)
 748 {
 749   ppl_Pointset_Powerset_C_Polyhedron_t po;
 750   ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
 751   graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1));
 752   graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1));
 753   ppl_dimension_type dim;
 754   bool empty_p;
 755   poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, false);
 756
 757   if (PDDR_KIND (pddr) == unknown_dependence)
 758     {
 759       free_poly_ddr (pddr);
 760       return true;
 761     }
 762
 763   if (pddr_is_empty (pddr))
 764     {
 765       free_poly_ddr (pddr);
 766       return false;
 767     }
 768
 769   po = PDDR_DDP (pddr);
 770   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
 771   eqpp = build_pairwise_scheduling (dim, level, 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