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