gcc/graphite-dependences.c

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