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