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.  When DIRECTION is set to
 300    1, compute the direct dependence from PDR1 to PDR2, and when
 301    DIRECTION is -1, compute the reversed dependence relation, from
 302    PDR2 to PDR1.  */
 303
 304 static void
 305 build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t *res,
 306                                        graphite_dim_t dim,
 307                                        graphite_dim_t tdim,
 308                                        graphite_dim_t offset,
 309                                        int direction)
 310 {
 311   graphite_dim_t i;
 312
 313   if (lexicographically_gt_p (*res, dim, offset, direction, 0))
 314     return;
 315
 316   for (i = 0; i < tdim - 1; i++)
 317     {
 318       ppl_Pointset_Powerset_C_Polyhedron_t sceq;
 319
 320       /* All the dimensions up to I are equal, ...  */
 321       sceq = build_pairwise_scheduling (dim, i, offset, 0);
 322       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, sceq);
 323       ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
 324
 325       /* ... and at depth I+1 they are not equal anymore.  */
 326       if (lexicographically_gt_p (*res, dim, offset, direction, i + 1))
 327         return;
 328     }
 329
 330   if (i == tdim - 1)
 331     {
 332       ppl_delete_Pointset_Powerset_C_Polyhedron (*res);
 333       ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res, dim, 1);
 334     }
 335 }
 336
 337 /* Build the dependence polyhedron for data references PDR1 and PDR2.
 338    The layout of the dependence polyhedron is:
 339
 340    T1|I1|T2|I2|S1|S2|G
 341
 342    with
 343    | T1 and T2 the scattering dimensions for PDR1 and PDR2
 344    | I1 and I2 the iteration domains
 345    | S1 and S2 the subscripts
 346    | G the global parameters.
 347
 348    D1 and D2 are the iteration domains of PDR1 and PDR2.
 349
 350    SCAT1 and SCAT2 are the scattering polyhedra for PDR1 and PDR2.
 351    When ORIGINAL_SCATTERING_P is true, then the scattering polyhedra
 352    SCAT1 and SCAT2 correspond to the original scattering of the
 353    program, otherwise they correspond to the transformed scattering.
 354
 355    When DIRECTION is set to 1, compute the direct dependence from PDR1
 356    to PDR2, and when DIRECTION is -1, compute the reversed dependence
 357    relation, from PDR2 to PDR1.  */
 358
 359 static poly_ddr_p
 360 dependence_polyhedron_1 (poly_bb_p pbb1, poly_bb_p pbb2,
 361                          ppl_Pointset_Powerset_C_Polyhedron_t d1,
 362                          ppl_Pointset_Powerset_C_Polyhedron_t d2,
 363                          poly_dr_p pdr1, poly_dr_p pdr2,
 364                          ppl_Polyhedron_t scat1, ppl_Polyhedron_t scat2,
 365                          int direction,
 366                          bool original_scattering_p)
 367 {
 368   scop_p scop = PBB_SCOP (pbb1);
 369   graphite_dim_t tdim1 = original_scattering_p ?
 370     pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
 371   graphite_dim_t tdim2 = original_scattering_p ?
 372     pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
 373   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 374   graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
 375   graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
 376   graphite_dim_t gdim = scop_nb_params (scop);
 377   graphite_dim_t dim1 = pdr_dim (pdr1);
 378   graphite_dim_t dim2 = pdr_dim (pdr2);
 379   graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim;
 380   ppl_Pointset_Powerset_C_Polyhedron_t res;
 381   ppl_Pointset_Powerset_C_Polyhedron_t id1, id2, isc1, isc2, idr1, idr2;
 382   ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
 383   ppl_Pointset_Powerset_C_Polyhedron_t context;
 384
 385   gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
 386
 387   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 388     (&context, SCOP_CONTEXT (scop));
 389   ppl_insert_dimensions_pointset (context, 0, dim - gdim);
 390
 391   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, scat1);
 392   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, scat2);
 393
 394   id1 = map_into_dep_poly (dim, gdim, d1, ddim1, tdim1);
 395   id2 = map_into_dep_poly (dim, gdim, d2, ddim2, tdim1 + ddim1 + tdim2);
 396   isc1 = map_into_dep_poly (dim, gdim, sc1, ddim1 + tdim1, 0);
 397   isc2 = map_into_dep_poly (dim, gdim, sc2, ddim2 + tdim2, tdim1 + ddim1);
 398
 399   idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
 400                                tdim1, tdim2 + ddim2);
 401   idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
 402                                tdim1 + ddim1 + tdim2, sdim1);
 403
 404   /* Now add the subscript equalities.  */
 405   dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
 406
 407   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
 408   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, context);
 409   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id1);
 410   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id2);
 411   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc1);
 412   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc2);
 413   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1);
 414   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
 415   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq);
 416   ppl_delete_Pointset_Powerset_C_Polyhedron (context);
 417   ppl_delete_Pointset_Powerset_C_Polyhedron (id1);
 418   ppl_delete_Pointset_Powerset_C_Polyhedron (id2);
 419   ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
 420   ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
 421   ppl_delete_Pointset_Powerset_C_Polyhedron (isc1);
 422   ppl_delete_Pointset_Powerset_C_Polyhedron (isc2);
 423   ppl_delete_Pointset_Powerset_C_Polyhedron (idr1);
 424   ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
 425   ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
 426
 427   if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
 428     build_lexicographically_gt_constraint (&res, dim, MIN (tdim1, tdim2),
 429                                            tdim1 + ddim1, direction);
 430
 431   return new_poly_ddr (pdr1, pdr2, res);
 432 }
 433
 434 /* Build the dependence polyhedron for data references PDR1 and PDR2.
 435    If possible use already cached information.
 436
 437    D1 and D2 are the iteration domains of PDR1 and PDR2.
 438
 439    SCAT1 and SCAT2 are the scattering polyhedra for PDR1 and PDR2.
 440    When ORIGINAL_SCATTERING_P is true, then the scattering polyhedra
 441    SCAT1 and SCAT2 correspond to the original scattering of the
 442    program, otherwise they correspond to the transformed scattering.
 443
 444    When DIRECTION is set to 1, compute the direct dependence from PDR1
 445    to PDR2, and when DIRECTION is -1, compute the reversed dependence
 446    relation, from PDR2 to PDR1.  */
 447
 448 static poly_ddr_p
 449 dependence_polyhedron (poly_bb_p pbb1, poly_bb_p pbb2,
 450                        ppl_Pointset_Powerset_C_Polyhedron_t d1,
 451                        ppl_Pointset_Powerset_C_Polyhedron_t d2,
 452                        poly_dr_p pdr1, poly_dr_p pdr2,
 453                        ppl_Polyhedron_t scat1, ppl_Polyhedron_t scat2,
 454                        int direction,
 455                        bool original_scattering_p)
 456 {
 457   PTR *x = NULL;
 458   poly_ddr_p res;
 459
 460   if (original_scattering_p)
 461     {
 462       struct poly_ddr tmp;
 463
 464       tmp.source = pdr1;
 465       tmp.sink = pdr2;
 466       x = htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1)),
 467                           &tmp, INSERT);
 468
 469       if (x && *x)
 470         return (poly_ddr_p) *x;
 471     }
 472
 473   res = dependence_polyhedron_1 (pbb1, pbb2, d1, d2, pdr1, pdr2,
 474                                  scat1, scat2, direction, original_scattering_p);
 475
 476   if (original_scattering_p)
 477     *x = res;
 478
 479   return res;
 480 }
 481
 482 /* Returns the Polyhedral Data Dependence Relation (PDDR) between PDR1
 483    contained in PBB1 and PDR2 contained in PBB2.  When
 484    ORIGINAL_SCATTERING_P is true, return the PDDR corresponding to the
 485    original scattering, or NULL if the dependence relation is empty.
 486    When ORIGINAL_SCATTERING_P is false, return the PDDR corresponding
 487    to the transformed scattering.  When DIRECTION is set to 1, compute
 488    the direct dependence from PDR1 to PDR2, and when DIRECTION is -1,
 489    compute the reversed dependence relation, from PDR2 to PDR1.  */
 490
 491 static poly_ddr_p
 492 build_pddr (poly_bb_p pbb1, poly_bb_p pbb2, poly_dr_p pdr1, poly_dr_p pdr2,
 493             int direction, bool original_scattering_p)
 494 {
 495   poly_ddr_p pddr;
 496   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 497   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 498   ppl_Polyhedron_t scat1 = original_scattering_p ?
 499     PBB_ORIGINAL_SCATTERING (pbb1) : PBB_TRANSFORMED_SCATTERING (pbb1);
 500   ppl_Polyhedron_t scat2 = original_scattering_p ?
 501     PBB_ORIGINAL_SCATTERING (pbb2) : PBB_TRANSFORMED_SCATTERING (pbb2);
 502
 503   if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
 504       || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
 505       || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
 506     return NULL;
 507
 508   pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, scat1, scat2,
 509                                 direction, original_scattering_p);
 510   if (pddr_is_empty (pddr))
 511     return NULL;
 512
 513   return pddr;
 514 }
 515
 516 /* Return true when the data dependence relation between the data
 517    references PDR1 belonging to PBB1 and PDR2 is part of a
 518    reduction.  */
 519
 520 static inline bool
 521 reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
 522 {
 523   int i;
 524   poly_dr_p pdr;
 525
 526   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
 527     if (PDR_TYPE (pdr) == PDR_WRITE)
 528       break;
 529
 530   return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
 531 }
 532
 533 /* Return true when the data dependence relation between the data
 534    references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
 535    part of a reduction.  */
 536
 537 static inline bool
 538 reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2,
 539                 poly_dr_p pdr1, poly_dr_p pdr2)
 540 {
 541   if (PBB_IS_REDUCTION (pbb1))
 542     return reduction_dr_1 (pbb1, pdr1, pdr2);
 543
 544   if (PBB_IS_REDUCTION (pbb2))
 545     return reduction_dr_1 (pbb2, pdr2, pdr1);
 546
 547   return false;
 548 }
 549
 550 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
 551    and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
 552    functions.  */
 553
 554 static bool
 555 graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
 556                              poly_dr_p pdr1, poly_dr_p pdr2)
 557 {
 558   ppl_Polyhedron_t st1, st2;
 559   ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
 560   graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
 561   ppl_Pointset_Powerset_C_Polyhedron_t temp;
 562   ppl_dimension_type pdim;
 563   bool is_empty_p;
 564   poly_ddr_p pddr;
 565
 566   if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
 567     return true;
 568
 569   pddr = build_pddr (pbb1, pbb2, pdr1, pdr2, 1, true);
 570   if (!pddr)
 571     /* There are no dependences between PDR1 and PDR2 in the original
 572        version of the program, so the transform is legal.  */
 573     return true;
 574
 575   po = PDDR_DDP (pddr);
 576
 577   if (dump_file && (dump_flags & TDF_DETAILS))
 578     fprintf (dump_file, "\nloop carries dependency.\n");
 579
 580   st1 = PBB_TRANSFORMED_SCATTERING (pbb1);
 581   st2 = PBB_TRANSFORMED_SCATTERING (pbb2);
 582   ddim1 = pbb_dim_iter_domain (pbb1);
 583   otdim1 = pbb_nb_scattering_orig (pbb1);
 584   otdim2 = pbb_nb_scattering_orig (pbb2);
 585   ttdim1 = pbb_nb_scattering_transform (pbb1);
 586   ttdim2 = pbb_nb_scattering_transform (pbb2);
 587
 588   /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
 589      Keep in mind, that PO polyhedron might be restored from the cache
 590      and should not be modified!  */
 591   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
 592   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp, pdim, 0);
 593   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, po);
 594
 595   /* We build the reverse dependence relation for the transformed
 596      scattering, such that when we intersect it with the original PO,
 597      we get an empty intersection when the transform is legal:
 598      i.e. the transform should reverse no dependences, and so PT, the
 599      reversed transformed PDDR, should have no constraint from PO.  */
 600   pddr = build_pddr (pbb1, pbb2, pdr1, pdr2, -1, false);
 601   if (!pddr)
 602     /* There are no dependences after the transform, so the transform
 603        is legal.  */
 604     return true;
 605
 606   pt = PDDR_DDP (pddr);
 607
 608   /* Extend PO and PT to have the same dimensions.  */
 609   ppl_insert_dimensions_pointset (temp, otdim1, ttdim1);
 610   ppl_insert_dimensions_pointset (temp, otdim1 + ttdim1 + ddim1 + otdim2, ttdim2);
 611   ppl_insert_dimensions_pointset (pt, 0, otdim1);
 612   ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
 613
 614   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, pt);
 615   is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp);
 616
 617   ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
 618   free_poly_ddr (pddr);
 619
 620   return is_empty_p;
 621 }
 622
 623 /* Return true when the data dependence relation for PBB1 and PBB2 is
 624    part of a reduction.  */
 625
 626 static inline bool
 627 reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
 628 {
 629   return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
 630 }
 631
 632 /* Iterates over the data references of PBB1 and PBB2 and detect
 633    whether the transformed schedule is correct.  */
 634
 635 static bool
 636 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
 637 {
 638   int i, j;
 639   poly_dr_p pdr1, pdr2;
 640
 641   if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
 642     pbb_remove_duplicate_pdrs (pbb1);
 643
 644   if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
 645     pbb_remove_duplicate_pdrs (pbb2);
 646
 647   if (reduction_ddr_p (pbb1, pbb2))
 648     return true;
 649
 650   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 651     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 652       if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
 653         return false;
 654
 655   return true;
 656 }
 657
 658 /* Iterates over the SCOP and detect whether the transformed schedule
 659    is correct.  */
 660
 661 bool
 662 graphite_legal_transform (scop_p scop)
 663 {
 664   int i, j;
 665   poly_bb_p pbb1, pbb2;
 666
 667   timevar_push (TV_GRAPHITE_DATA_DEPS);
 668
 669   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 670     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 671       if (!graphite_legal_transform_bb (pbb1, pbb2))
 672         {
 673           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 674           return false;
 675         }
 676
 677   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 678   return true;
 679 }
 680
 681 /* Remove all the dimensions except alias information at dimension
 682    ALIAS_DIM.  */
 683
 684 static void
 685 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
 686                           ppl_dimension_type alias_dim)
 687 {
 688   ppl_dimension_type *ds;
 689   ppl_dimension_type access_dim;
 690   unsigned i, pos = 0;
 691
 692   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
 693                                                       &access_dim);
 694   ds = XNEWVEC (ppl_dimension_type, access_dim-1);
 695   for (i = 0; i < access_dim; i++)
 696     {
 697       if (i == alias_dim)
 698         continue;
 699
 700       ds[pos] = i;
 701       pos++;
 702     }
 703
 704   ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
 705                                                               ds,
 706                                                               access_dim - 1);
 707   free (ds);
 708 }
 709
 710 /* Return true when PDR1 and PDR2 may alias.  */
 711
 712 static bool
 713 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
 714 {
 715   ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
 716   ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
 717   ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
 718   ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
 719   ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
 720   int empty_p;
 721
 722   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 723     (&alias_powerset1, accesses1);
 724   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 725     (&alias_powerset2, accesses2);
 726
 727   build_alias_set_powerset (alias_powerset1, alias_dim1);
 728   build_alias_set_powerset (alias_powerset2, alias_dim2);
 729
 730   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
 731     (alias_powerset1, alias_powerset2);
 732
 733   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
 734
 735   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
 736   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
 737
 738   return !empty_p;
 739 }
 740
 741 /* Returns TRUE when the dependence polyhedron between PDR1 and
 742    PDR2 represents a loop carried dependence at level LEVEL.  */
 743
 744 static bool
 745 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
 746                                      int level)
 747 {
 748   poly_bb_p pbb1 = PDR_PBB (pdr1);
 749   poly_bb_p pbb2 = PDR_PBB (pdr2);
 750   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 751   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 752   ppl_Polyhedron_t so1 = PBB_TRANSFORMED_SCATTERING (pbb1);
 753   ppl_Polyhedron_t so2 = PBB_TRANSFORMED_SCATTERING (pbb2);
 754   ppl_Pointset_Powerset_C_Polyhedron_t po;
 755   ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
 756   graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
 757   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 758   ppl_dimension_type dim;
 759   bool empty_p;
 760   poly_ddr_p pddr;
 761   int obj_base_set1 = PDR_BASE_OBJECT_SET (pdr1);
 762   int obj_base_set2 = PDR_BASE_OBJECT_SET (pdr2);
 763
 764   if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
 765       || !poly_drs_may_alias_p (pdr1, pdr2))
 766     return false;
 767
 768   if (obj_base_set1 != obj_base_set2)
 769     return true;
 770
 771   if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
 772     return false;
 773
 774   pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
 775                                 1, false);
 776
 777   if (pddr_is_empty (pddr))
 778     return false;
 779
 780   po = PDDR_DDP (pddr);
 781   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
 782   eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1);
 783
 784   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
 785   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
 786
 787   ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
 788   return !empty_p;
 789 }
 790
 791 /* Check data dependency between PBB1 and PBB2 at level LEVEL.  */
 792
 793 bool
 794 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
 795 {
 796   int i, j;
 797   poly_dr_p pdr1, pdr2;
 798
 799   timevar_push (TV_GRAPHITE_DATA_DEPS);
 800
 801   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 802     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 803       if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
 804         {
 805           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 806           return true;
 807         }
 808
 809   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 810   return false;
 811 }
 812
 813 /* Pretty print to FILE all the original data dependences of SCoP in
 814    DOT format.  */
 815
 816 static void
 817 dot_original_deps_stmt_1 (FILE *file, scop_p scop)
 818 {
 819   int i, j, k, l;
 820   poly_bb_p pbb1, pbb2;
 821   poly_dr_p pdr1, pdr2;
 822
 823   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 824     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 825       {
 826         for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 827           for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 828             if (build_pddr (pbb1, pbb2, pdr1, pdr2, 1, true))
 829               {
 830                 fprintf (file, "OS%d -> OS%d\n",
 831                          pbb_index (pbb1), pbb_index (pbb2));
 832                 goto done;
 833               }
 834       done:;
 835       }
 836 }
 837
 838 /* Pretty print to FILE all the transformed data dependences of SCoP in
 839    DOT format.  */
 840
 841 static void
 842 dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
 843 {
 844   int i, j, k, l;
 845   poly_bb_p pbb1, pbb2;
 846   poly_dr_p pdr1, pdr2;
 847   poly_ddr_p pddr;
 848
 849   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 850     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 851       {
 852         for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 853           for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 854             if ((pddr = build_pddr (pbb1, pbb2, pdr1, pdr2, 1, false)))
 855               {
 856                 fprintf (file, "TS%d -> TS%d\n",
 857                          pbb_index (pbb1), pbb_index (pbb2));
 858                 free_poly_ddr (pddr);
 859                 goto done;
 860               }
 861       done:;
 862       }
 863 }
 864
 865
 866 /* Pretty print to FILE all the data dependences of SCoP in DOT
 867    format.  */
 868
 869 static void
 870 dot_deps_stmt_1 (FILE *file, scop_p scop)
 871 {
 872   fputs ("digraph all {\n", file);
 873
 874   dot_original_deps_stmt_1 (file, scop);
 875   dot_transformed_deps_stmt_1 (file, scop);
 876
 877   fputs ("}\n\n", file);
 878 }
 879
 880 /* Pretty print to FILE all the original data dependences of SCoP in
 881    DOT format.  */
 882
 883 static void
 884 dot_original_deps (FILE *file, scop_p scop)
 885 {
 886   int i, j, k, l;
 887   poly_bb_p pbb1, pbb2;
 888   poly_dr_p pdr1, pdr2;
 889
 890   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 891     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 892       for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 893         for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 894           if (build_pddr (pbb1, pbb2, pdr1, pdr2, 1, true))
 895             fprintf (file, "OS%d_D%d -> OS%d_D%d\n",
 896                      pbb_index (pbb1), PDR_ID (pdr1),
 897                      pbb_index (pbb2), PDR_ID (pdr2));
 898 }
 899
 900 /* Pretty print to FILE all the transformed data dependences of SCoP in
 901    DOT format.  */
 902
 903 static void
 904 dot_transformed_deps (FILE *file, scop_p scop)
 905 {
 906   int i, j, k, l;
 907   poly_bb_p pbb1, pbb2;
 908   poly_dr_p pdr1, pdr2;
 909   poly_ddr_p pddr;
 910
 911   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 912     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 913       for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 914         for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 915           if ((pddr = build_pddr (pbb1, pbb2, pdr1, pdr2, 1, false)))
 916             {
 917               fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
 918                        pbb_index (pbb1), PDR_ID (pdr1),
 919                        pbb_index (pbb2), PDR_ID (pdr2));
 920               free_poly_ddr (pddr);
 921             }
 922 }
 923
 924 /* Pretty print to FILE all the data dependences of SCoP in DOT
 925    format.  */
 926
 927 static void
 928 dot_deps_1 (FILE *file, scop_p scop)
 929 {
 930   fputs ("digraph all {\n", file);
 931
 932   dot_original_deps (file, scop);
 933   dot_transformed_deps (file, scop);
 934
 935   fputs ("}\n\n", file);
 936 }
 937
 938 /* Display all the data dependences in SCoP using dotty.  */
 939
 940 void
 941 dot_deps (scop_p scop)
 942 {
 943   /* When debugging, enable the following code.  This cannot be used
 944      in production compilers because it calls "system".  */
 945 #if 0
 946   int x;
 947   FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
 948   gcc_assert (stream);
 949
 950   dot_deps_1 (stream, scop);
 951   fclose (stream);
 952
 953   x = system ("dotty /tmp/scopdeps.dot");
 954 #else
 955   dot_deps_1 (stderr, scop);
 956 #endif
 957 }
 958
 959 /* Display all the statement dependences in SCoP using dotty.  */
 960
 961 void
 962 dot_deps_stmt (scop_p scop)
 963 {
 964   /* When debugging, enable the following code.  This cannot be used
 965      in production compilers because it calls "system".  */
 966 #if 0
 967   int x;
 968   FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
 969   gcc_assert (stream);
 970
 971   dot_deps_stmt_1 (stream, scop);
 972   fclose (stream);
 973
 974   x = system ("dotty /tmp/scopdeps.dot");
 975 #else
 976   dot_deps_stmt_1 (stderr, scop);
 977 #endif
 978 }
 979
 980 #endif