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