contrib/gcc-4.7/gcc/graphite-dependences.c

   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