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 "cloog/cloog.h"
  46 #include "ppl_c.h"
  47 #include "sese.h"
  48 #include "graphite-ppl.h"
  49 #include "graphite.h"
  50 #include "graphite-poly.h"
  51 #include "graphite-dependences.h"
  52
  53 /* Returns a new polyhedral Data Dependence Relation (DDR).  SOURCE is
  54    the source data reference, SINK is the sink data reference.  When
  55    the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE
  56    and SINK are in dependence as described by DDP.  */
  57
  58 static poly_ddr_p
  59 new_poly_ddr (poly_dr_p source, poly_dr_p sink,
  60               ppl_Pointset_Powerset_C_Polyhedron_t ddp,
  61               bool original_scattering_p)
  62 {
  63   poly_ddr_p pddr = XNEW (struct poly_ddr);
  64
  65   PDDR_SOURCE (pddr) = source;
  66   PDDR_SINK (pddr) = sink;
  67   PDDR_DDP (pddr) = ddp;
  68   PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
  69
  70   if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
  71     PDDR_KIND (pddr) = no_dependence;
  72   else
  73     PDDR_KIND (pddr) = has_dependence;
  74
  75   return pddr;
  76 }
  77
  78 /* Free the poly_ddr_p P.  */
  79
  80 void
  81 free_poly_ddr (void *p)
  82 {
  83   poly_ddr_p pddr = (poly_ddr_p) p;
  84   ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
  85   free (pddr);
  86 }
  87
  88 /* Comparison function for poly_ddr hash table.  */
  89
  90 int
  91 eq_poly_ddr_p (const void *pddr1, const void *pddr2)
  92 {
  93   const struct poly_ddr *p1 = (const struct poly_ddr *) pddr1;
  94   const struct poly_ddr *p2 = (const struct poly_ddr *) pddr2;
  95
  96   return (PDDR_SOURCE (p1) == PDDR_SOURCE (p2)
  97           && PDDR_SINK (p1) == PDDR_SINK (p2));
  98 }
  99
 100 /* Hash function for poly_ddr hashtable.  */
 101
 102 hashval_t
 103 hash_poly_ddr_p (const void *pddr)
 104 {
 105   const struct poly_ddr *p = (const struct poly_ddr *) pddr;
 106
 107   return (hashval_t) ((long) PDDR_SOURCE (p) + (long) PDDR_SINK (p));
 108 }
 109
 110 /* Returns true when PDDR has no dependence.  */
 111
 112 static bool
 113 pddr_is_empty (poly_ddr_p pddr)
 114 {
 115   if (!pddr)
 116     return true;
 117
 118   gcc_assert (PDDR_KIND (pddr) != unknown_dependence);
 119
 120   return PDDR_KIND (pddr) == no_dependence ? true : false;
 121 }
 122
 123 /* Prints to FILE the layout of the dependence polyhedron of PDDR:
 124
 125    T1|I1|T2|I2|S1|S2|G
 126
 127    with
 128    | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK
 129    | I1 and I2 the iteration domains
 130    | S1 and S2 the subscripts
 131    | G the global parameters.  */
 132
 133 static void
 134 print_dependence_polyhedron_layout (FILE *file, poly_ddr_p pddr)
 135 {
 136   poly_dr_p pdr1 = PDDR_SOURCE (pddr);
 137   poly_dr_p pdr2 = PDDR_SINK (pddr);
 138   poly_bb_p pbb1 = PDR_PBB (pdr1);
 139   poly_bb_p pbb2 = PDR_PBB (pdr2);
 140
 141   graphite_dim_t i;
 142   graphite_dim_t tdim1 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
 143     pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
 144   graphite_dim_t tdim2 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
 145     pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
 146   graphite_dim_t idim1 = pbb_dim_iter_domain (pbb1);
 147   graphite_dim_t idim2 = pbb_dim_iter_domain (pbb2);
 148   graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
 149   graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
 150   graphite_dim_t gdim = scop_nb_params (PBB_SCOP (pbb1));
 151
 152   fprintf (file, "#  eq");
 153
 154   for (i = 0; i < tdim1; i++)
 155     fprintf (file, "   t1_%d", (int) i);
 156   for (i = 0; i < idim1; i++)
 157     fprintf (file, "   i1_%d", (int) i);
 158   for (i = 0; i < tdim2; i++)
 159     fprintf (file, "   t2_%d", (int) i);
 160   for (i = 0; i < idim2; i++)
 161     fprintf (file, "   i2_%d", (int) i);
 162   for (i = 0; i < sdim1; i++)
 163     fprintf (file, "   s1_%d", (int) i);
 164   for (i = 0; i < sdim2; i++)
 165     fprintf (file, "   s2_%d", (int) i);
 166   for (i = 0; i < gdim; i++)
 167     fprintf (file, "    g_%d", (int) i);
 168
 169   fprintf (file, "    cst\n");
 170 }
 171
 172 /* Prints to FILE the poly_ddr_p PDDR.  */
 173
 174 void
 175 print_pddr (FILE *file, poly_ddr_p pddr)
 176 {
 177   fprintf (file, "pddr (kind: ");
 178
 179   if (PDDR_KIND (pddr) == unknown_dependence)
 180     fprintf (file, "unknown_dependence");
 181   else if (PDDR_KIND (pddr) == no_dependence)
 182     fprintf (file, "no_dependence");
 183   else if (PDDR_KIND (pddr) == has_dependence)
 184     fprintf (file, "has_dependence");
 185
 186   fprintf (file, "\n  source ");
 187   print_pdr (file, PDDR_SOURCE (pddr), 2);
 188
 189   fprintf (file, "\n  sink ");
 190   print_pdr (file, PDDR_SINK (pddr), 2);
 191
 192   if (PDDR_KIND (pddr) == has_dependence)
 193     {
 194       fprintf (file, "\n  dependence polyhedron (\n");
 195       print_dependence_polyhedron_layout (file, pddr);
 196       ppl_print_powerset_matrix (file, PDDR_DDP (pddr));
 197       fprintf (file, ")\n");
 198     }
 199
 200   fprintf (file, ")\n");
 201 }
 202
 203 /* Prints to STDERR the poly_ddr_p PDDR.  */
 204
 205 void
 206 debug_pddr (poly_ddr_p pddr)
 207 {
 208   print_pddr (stderr, pddr);
 209 }
 210
 211
 212 /* Remove all the dimensions except alias information at dimension
 213    ALIAS_DIM.  */
 214
 215 static void
 216 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
 217                           ppl_dimension_type alias_dim)
 218 {
 219   ppl_dimension_type *ds;
 220   ppl_dimension_type access_dim;
 221   unsigned i, pos = 0;
 222
 223   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
 224                                                       &access_dim);
 225   ds = XNEWVEC (ppl_dimension_type, access_dim-1);
 226   for (i = 0; i < access_dim; i++)
 227     {
 228       if (i == alias_dim)
 229         continue;
 230
 231       ds[pos] = i;
 232       pos++;
 233     }
 234
 235   ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
 236                                                               ds,
 237                                                               access_dim - 1);
 238   free (ds);
 239 }
 240
 241 /* Return true when PDR1 and PDR2 may alias.  */
 242
 243 static bool
 244 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
 245 {
 246   ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
 247   ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
 248   ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
 249   ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
 250   ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
 251   int empty_p;
 252
 253   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 254     (&alias_powerset1, accesses1);
 255   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 256     (&alias_powerset2, accesses2);
 257
 258   build_alias_set_powerset (alias_powerset1, alias_dim1);
 259   build_alias_set_powerset (alias_powerset2, alias_dim2);
 260
 261   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
 262     (alias_powerset1, alias_powerset2);
 263
 264   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
 265
 266   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
 267   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
 268
 269   return !empty_p;
 270 }
 271
 272 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
 273    transformed into "a CUT0 c CUT1' b"
 274
 275    Add NB0 zeros before "a":  "00...0 a CUT0 c CUT1' b"
 276    Add NB1 zeros between "a" and "c":  "00...0 a 00...0 c CUT1' b"
 277    Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
 278    "00...0 a 00...0 c 00...0 b".  */
 279
 280 static ppl_Pointset_Powerset_C_Polyhedron_t
 281 map_dr_into_dep_poly (graphite_dim_t dim,
 282                       ppl_Pointset_Powerset_C_Polyhedron_t dr,
 283                       graphite_dim_t cut0, graphite_dim_t cut1,
 284                       graphite_dim_t nb0, graphite_dim_t nb1)
 285 {
 286   ppl_dimension_type pdim;
 287   ppl_dimension_type *map;
 288   ppl_Pointset_Powerset_C_Polyhedron_t res;
 289   ppl_dimension_type i;
 290
 291   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 292     (&res, dr);
 293   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim);
 294
 295   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim);
 296
 297   /* First mapping: move 'g' vector to right position.  */
 298   for (i = 0; i < cut0; i++)
 299     map[i] = i;
 300
 301   for (i = cut0; i < cut1; i++)
 302     map[i] = pdim - cut1 + i;
 303
 304   for (i = cut1; i < pdim; i++)
 305     map[i] = cut0 + i - cut1;
 306
 307   ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim);
 308   free (map);
 309
 310   /* After swapping 's' and 'g' vectors, we have to update a new cut.  */
 311   cut1 = pdim - cut1 + cut0;
 312
 313   ppl_insert_dimensions_pointset (res, 0, nb0);
 314   ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1);
 315   ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1,
 316                                   dim - nb0 - nb1 - pdim);
 317
 318   return res;
 319 }
 320
 321 /* Builds subscript equality constraints.  */
 322
 323 static ppl_Pointset_Powerset_C_Polyhedron_t
 324 dr_equality_constraints (graphite_dim_t dim,
 325                          graphite_dim_t pos, graphite_dim_t nb_subscripts)
 326 {
 327   ppl_Polyhedron_t eqs;
 328   ppl_Pointset_Powerset_C_Polyhedron_t res;
 329   graphite_dim_t i;
 330
 331   ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0);
 332
 333   for (i = 0; i < nb_subscripts; i++)
 334     {
 335       ppl_Constraint_t cstr
 336         = ppl_build_relation (dim, pos + i, pos + i + nb_subscripts,
 337                               0, PPL_CONSTRAINT_TYPE_EQUAL);
 338       ppl_Polyhedron_add_constraint (eqs, cstr);
 339       ppl_delete_Constraint (cstr);
 340     }
 341
 342   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs);
 343   ppl_delete_Polyhedron (eqs);
 344   return res;
 345 }
 346
 347 /* Builds scheduling inequality constraints: when DIRECTION is
 348    1 builds a GE constraint,
 349    0 builds an EQ constraint,
 350    -1 builds a LE constraint.  */
 351
 352 static ppl_Pointset_Powerset_C_Polyhedron_t
 353 build_pairwise_scheduling (graphite_dim_t dim,
 354                            graphite_dim_t pos,
 355                            graphite_dim_t offset,
 356                            int direction)
 357 {
 358   ppl_Pointset_Powerset_C_Polyhedron_t res;
 359   ppl_Polyhedron_t equalities;
 360   ppl_Constraint_t cstr;
 361
 362   ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
 363
 364   switch (direction)
 365     {
 366     case -1:
 367       cstr = ppl_build_relation (dim, pos, pos + offset, 1,
 368                                  PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
 369       break;
 370
 371     case 0:
 372       cstr = ppl_build_relation (dim, pos, pos + offset, 0,
 373                                  PPL_CONSTRAINT_TYPE_EQUAL);
 374       break;
 375
 376     case 1:
 377       cstr = ppl_build_relation (dim, pos, pos + offset, -1,
 378                                  PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 379       break;
 380
 381     default:
 382       gcc_unreachable ();
 383     }
 384
 385   ppl_Polyhedron_add_constraint (equalities, cstr);
 386   ppl_delete_Constraint (cstr);
 387
 388   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
 389   ppl_delete_Polyhedron (equalities);
 390   return res;
 391 }
 392
 393 /* Add to a non empty polyhedron BAG the precedence constraints for
 394    the lexicographical comparison of time vectors in BAG following the
 395    lexicographical order.  DIM is the dimension of the polyhedron BAG.
 396    TDIM is the number of loops common to the two statements that are
 397    compared lexicographically, i.e. the number of loops containing
 398    both statements.  OFFSET is the number of dimensions needed to
 399    represent the first statement, i.e. dimT1 + dimI1 in the layout of
 400    the BAG polyhedron: T1|I1|T2|I2|S1|S2|G.  When DIRECTION is set to
 401    1, compute the direct dependence from PDR1 to PDR2, and when
 402    DIRECTION is -1, compute the reversed dependence relation, from
 403    PDR2 to PDR1.  */
 404
 405 static ppl_Pointset_Powerset_C_Polyhedron_t
 406 build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
 407                                   graphite_dim_t dim,
 408                                   graphite_dim_t tdim,
 409                                   graphite_dim_t offset,
 410                                   int direction)
 411 {
 412   graphite_dim_t i;
 413   ppl_Pointset_Powerset_C_Polyhedron_t res, lex;
 414
 415   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1);
 416
 417   lex = build_pairwise_scheduling (dim, 0, offset, direction);
 418   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
 419
 420   if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
 421     ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
 422
 423   ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
 424
 425   for (i = 0; i < tdim - 1; i++)
 426     {
 427       ppl_Pointset_Powerset_C_Polyhedron_t sceq;
 428
 429       sceq = build_pairwise_scheduling (dim, i, offset, 0);
 430       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
 431       ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
 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_Pointset_Powerset_C_Polyhedron_is_empty (lex))
 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_Pointset_Powerset_C_Polyhedron_is_empty (res))
 516     {
 517       ppl_Pointset_Powerset_C_Polyhedron_t lex =
 518         build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
 519                                           tdim1 + ddim1, 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 (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
 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_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
 689
 690   ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
 691   free_poly_ddr (tpddr);
 692
 693   if (dump_file && (dump_flags & TDF_DETAILS))
 694     fprintf (dump_file, "\nloop carries dependency.\n");
 695
 696   return is_empty_p;
 697 }
 698
 699 /* Return true when the data dependence relation for PBB1 and PBB2 is
 700    part of a reduction.  */
 701
 702 static inline bool
 703 reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
 704 {
 705   return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
 706 }
 707
 708 /* Iterates over the data references of PBB1 and PBB2 and detect
 709    whether the transformed schedule is correct.  */
 710
 711 static bool
 712 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
 713 {
 714   int i, j;
 715   poly_dr_p pdr1, pdr2;
 716
 717   if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
 718     pbb_remove_duplicate_pdrs (pbb1);
 719
 720   if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
 721     pbb_remove_duplicate_pdrs (pbb2);
 722
 723   if (reduction_ddr_p (pbb1, pbb2))
 724     return true;
 725
 726   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 727     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 728       if (!graphite_legal_transform_dr (pdr1, pdr2))
 729         return false;
 730
 731   return true;
 732 }
 733
 734 /* Iterates over the SCOP and detect whether the transformed schedule
 735    is correct.  */
 736
 737 bool
 738 graphite_legal_transform (scop_p scop)
 739 {
 740   int i, j;
 741   poly_bb_p pbb1, pbb2;
 742
 743   timevar_push (TV_GRAPHITE_DATA_DEPS);
 744
 745   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 746     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 747       if (!graphite_legal_transform_bb (pbb1, pbb2))
 748         {
 749           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 750           return false;
 751         }
 752
 753   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 754   return true;
 755 }
 756
 757 /* Returns TRUE when the dependence polyhedron between PDR1 and
 758    PDR2 represents a loop carried dependence at level LEVEL.  */
 759
 760 static bool
 761 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
 762                                      int level)
 763 {
 764   ppl_Pointset_Powerset_C_Polyhedron_t po;
 765   ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
 766   graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1));
 767   graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1));
 768   ppl_dimension_type dim;
 769   bool empty_p;
 770   poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
 771
 772   if (PDDR_KIND (pddr) == unknown_dependence)
 773     {
 774       free_poly_ddr (pddr);
 775       return true;
 776     }
 777
 778   if (pddr_is_empty (pddr))
 779     {
 780       free_poly_ddr (pddr);
 781       return false;
 782     }
 783
 784   po = PDDR_DDP (pddr);
 785   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
 786   eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1);
 787
 788   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
 789   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
 790
 791   ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
 792   free_poly_ddr (pddr);
 793
 794   return !empty_p;
 795 }
 796
 797 /* Check data dependency between PBB1 and PBB2 at level LEVEL.  */
 798
 799 bool
 800 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
 801 {
 802   int i, j;
 803   poly_dr_p pdr1, pdr2;
 804
 805   timevar_push (TV_GRAPHITE_DATA_DEPS);
 806
 807   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 808     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 809       if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
 810         {
 811           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 812           return true;
 813         }
 814
 815   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 816   return false;
 817 }
 818
 819 /* Pretty print to FILE all the original data dependences of SCoP in
 820    DOT format.  */
 821
 822 static void
 823 dot_original_deps_stmt_1 (FILE *file, scop_p scop)
 824 {
 825   int i, j, k, l;
 826   poly_bb_p pbb1, pbb2;
 827   poly_dr_p pdr1, pdr2;
 828
 829   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 830     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 831       {
 832         for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 833           for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 834             if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
 835               {
 836                 fprintf (file, "OS%d -> OS%d\n",
 837                          pbb_index (pbb1), pbb_index (pbb2));
 838                 goto done;
 839               }
 840       done:;
 841       }
 842 }
 843
 844 /* Pretty print to FILE all the transformed data dependences of SCoP in
 845    DOT format.  */
 846
 847 static void
 848 dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
 849 {
 850   int i, j, k, l;
 851   poly_bb_p pbb1, pbb2;
 852   poly_dr_p pdr1, pdr2;
 853
 854   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 855     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 856       {
 857         for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 858           for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 859             {
 860               poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
 861
 862               if (!pddr_is_empty (pddr))
 863                 {
 864                   fprintf (file, "TS%d -> TS%d\n",
 865                            pbb_index (pbb1), pbb_index (pbb2));
 866
 867                   free_poly_ddr (pddr);
 868                   goto done;
 869                 }
 870
 871               free_poly_ddr (pddr);
 872             }
 873       done:;
 874       }
 875 }
 876
 877
 878 /* Pretty print to FILE all the data dependences of SCoP in DOT
 879    format.  */
 880
 881 static void
 882 dot_deps_stmt_1 (FILE *file, scop_p scop)
 883 {
 884   fputs ("digraph all {\n", file);
 885
 886   dot_original_deps_stmt_1 (file, scop);
 887   dot_transformed_deps_stmt_1 (file, scop);
 888
 889   fputs ("}\n\n", file);
 890 }
 891
 892 /* Pretty print to FILE all the original data dependences of SCoP in
 893    DOT format.  */
 894
 895 static void
 896 dot_original_deps (FILE *file, scop_p scop)
 897 {
 898   int i, j, k, l;
 899   poly_bb_p pbb1, pbb2;
 900   poly_dr_p pdr1, pdr2;
 901
 902   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 903     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 904       for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 905         for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 906           if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
 907             fprintf (file, "OS%d_D%d -> OS%d_D%d\n",
 908                      pbb_index (pbb1), PDR_ID (pdr1),
 909                      pbb_index (pbb2), PDR_ID (pdr2));
 910 }
 911
 912 /* Pretty print to FILE all the transformed data dependences of SCoP in
 913    DOT format.  */
 914
 915 static void
 916 dot_transformed_deps (FILE *file, scop_p scop)
 917 {
 918   int i, j, k, l;
 919   poly_bb_p pbb1, pbb2;
 920   poly_dr_p pdr1, pdr2;
 921
 922   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 923     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 924       for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 925         for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 926           {
 927             poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
 928
 929             if (!pddr_is_empty (pddr))
 930               fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
 931                        pbb_index (pbb1), PDR_ID (pdr1),
 932                        pbb_index (pbb2), PDR_ID (pdr2));
 933
 934             free_poly_ddr (pddr);
 935           }
 936 }
 937
 938 /* Pretty print to FILE all the data dependences of SCoP in DOT
 939    format.  */
 940
 941 static void
 942 dot_deps_1 (FILE *file, scop_p scop)
 943 {
 944   fputs ("digraph all {\n", file);
 945
 946   dot_original_deps (file, scop);
 947   dot_transformed_deps (file, scop);
 948
 949   fputs ("}\n\n", file);
 950 }
 951
 952 /* Display all the data dependences in SCoP using dotty.  */
 953
 954 void
 955 dot_deps (scop_p scop)
 956 {
 957   /* When debugging, enable the following code.  This cannot be used
 958      in production compilers because it calls "system".  */
 959 #if 0
 960   int x;
 961   FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
 962   gcc_assert (stream);
 963
 964   dot_deps_1 (stream, scop);
 965   fclose (stream);
 966
 967   x = system ("dotty /tmp/scopdeps.dot");
 968 #else
 969   dot_deps_1 (stderr, scop);
 970 #endif
 971 }
 972
 973 /* Display all the statement dependences in SCoP using dotty.  */
 974
 975 void
 976 dot_deps_stmt (scop_p scop)
 977 {
 978   /* When debugging, enable the following code.  This cannot be used
 979      in production compilers because it calls "system".  */
 980 #if 0
 981   int x;
 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   x = system ("dotty /tmp/scopdeps.dot");
 989 #else
 990   dot_deps_stmt_1 (stderr, scop);
 991 #endif
 992 }
 993
 994 #endif