gcc/graphite-dependences.c

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