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