gcc/graphite-dependences.c

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