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