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