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 /* Creates a new polyhedral data reference pair and
  54    returns it.  Parameter SOURCE denotes a source data reference
  55    while parameter SINK denotes a sink data reference.  Both
  56    SOURCE and SINK define a pair of references, thus they
  57    define an edge in DDG (Data Dependence Graph).  */
  58
  59 static poly_dr_pair_p
  60 new_poly_dr_pair (poly_dr_p source,
  61                   poly_dr_p sink,
  62                   ppl_Pointset_Powerset_C_Polyhedron_t ddp)
  63 {
  64   poly_dr_pair_p pdrpp;
  65
  66   pdrpp = XNEW (struct poly_dr_pair);
  67   pdrpp->source = source;
  68   pdrpp->sink = sink;
  69   pdrpp->ddp = ddp;
  70
  71   return pdrpp;
  72 }
  73
  74 /* Comparison function for poly_dr_pair hash table.  */
  75
  76 int
  77 eq_poly_dr_pair_p (const void *pdrpp1, const void *pdrpp2)
  78 {
  79   const struct poly_dr_pair *p1 = (const struct poly_dr_pair *) pdrpp1;
  80   const struct poly_dr_pair *p2 = (const struct poly_dr_pair *) pdrpp2;
  81
  82   return (p1->source == p2->source
  83           && p1->sink == p2->sink);
  84 }
  85
  86 /* Hash function for poly_dr_pair hashtable.  */
  87
  88 hashval_t
  89 hash_poly_dr_pair_p (const void *pdrpp)
  90 {
  91   const struct poly_dr_pair *p = (const struct poly_dr_pair *) pdrpp;
  92
  93   return (hashval_t) ((long) p->source + (long) p->sink);
  94 }
  95
  96 /* Returns a polyhedron of dimension DIM.
  97
  98    Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET0
  99    and the dimensions [cut, ..., nb_dim] to DIM - GDIM.  */
 100
 101 static ppl_Pointset_Powerset_C_Polyhedron_t
 102 map_into_dep_poly (graphite_dim_t dim, graphite_dim_t gdim,
 103                    ppl_Pointset_Powerset_C_Polyhedron_t p,
 104                    graphite_dim_t cut,
 105                    graphite_dim_t offset)
 106 {
 107   ppl_Pointset_Powerset_C_Polyhedron_t res;
 108
 109   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 110     (&res, p);
 111   ppl_insert_dimensions_pointset (res, 0, offset);
 112   ppl_insert_dimensions_pointset (res, offset + cut,
 113                                   dim - offset - cut - gdim);
 114
 115   return res;
 116 }
 117
 118 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
 119    transformed into "a CUT0 c CUT1' b"
 120
 121    Add NB0 zeros before "a":  "00...0 a CUT0 c CUT1' b"
 122    Add NB1 zeros between "a" and "c":  "00...0 a 00...0 c CUT1' b"
 123    Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
 124    "00...0 a 00...0 c 00...0 b".  */
 125
 126 static ppl_Pointset_Powerset_C_Polyhedron_t
 127 map_dr_into_dep_poly (graphite_dim_t dim,
 128                       ppl_Pointset_Powerset_C_Polyhedron_t dr,
 129                       graphite_dim_t cut0, graphite_dim_t cut1,
 130                       graphite_dim_t nb0, graphite_dim_t nb1)
 131 {
 132   ppl_dimension_type pdim;
 133   ppl_dimension_type *map;
 134   ppl_Pointset_Powerset_C_Polyhedron_t res;
 135   ppl_dimension_type i;
 136
 137   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 138     (&res, dr);
 139   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim);
 140
 141   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim);
 142
 143   /* First mapping: move 'g' vector to right position.  */
 144   for (i = 0; i < cut0; i++)
 145     map[i] = i;
 146
 147   for (i = cut0; i < cut1; i++)
 148     map[i] = pdim - cut1 + i;
 149
 150   for (i = cut1; i < pdim; i++)
 151     map[i] = cut0 + i - cut1;
 152
 153   ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim);
 154   free (map);
 155
 156   /* After swapping 's' and 'g' vectors, we have to update a new cut.  */
 157   cut1 = pdim - cut1 + cut0;
 158
 159   ppl_insert_dimensions_pointset (res, 0, nb0);
 160   ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1);
 161   ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1,
 162                                   dim - nb0 - nb1 - pdim);
 163
 164   return res;
 165 }
 166
 167 /* Builds a constraints of the form "POS1 - POS2 CSTR_TYPE C" */
 168
 169 static ppl_Constraint_t
 170 build_pairwise_constraint (graphite_dim_t dim,
 171                            graphite_dim_t pos1, graphite_dim_t pos2,
 172                            int c, enum ppl_enum_Constraint_Type cstr_type)
 173 {
 174   ppl_Linear_Expression_t expr;
 175   ppl_Constraint_t cstr;
 176   ppl_Coefficient_t coef;
 177   Value v, v_op, v_c;
 178
 179   value_init (v);
 180   value_init (v_op);
 181   value_init (v_c);
 182
 183   value_set_si (v, 1);
 184   value_set_si (v_op, -1);
 185   value_set_si (v_c, c);
 186
 187   ppl_new_Coefficient (&coef);
 188   ppl_new_Linear_Expression_with_dimension (&expr, dim);
 189
 190   ppl_assign_Coefficient_from_mpz_t (coef, v);
 191   ppl_Linear_Expression_add_to_coefficient (expr, pos1, coef);
 192   ppl_assign_Coefficient_from_mpz_t (coef, v_op);
 193   ppl_Linear_Expression_add_to_coefficient (expr, pos2, coef);
 194   ppl_assign_Coefficient_from_mpz_t (coef, v_c);
 195   ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
 196
 197   ppl_new_Constraint (&cstr, expr, cstr_type);
 198
 199   ppl_delete_Linear_Expression (expr);
 200   ppl_delete_Coefficient (coef);
 201   value_clear (v);
 202   value_clear (v_op);
 203   value_clear (v_c);
 204
 205   return cstr;
 206 }
 207
 208 /* Builds subscript equality constraints.  */
 209
 210 static ppl_Pointset_Powerset_C_Polyhedron_t
 211 dr_equality_constraints (graphite_dim_t dim,
 212                          graphite_dim_t pos, graphite_dim_t nb_subscripts)
 213 {
 214   ppl_Polyhedron_t subscript_equalities;
 215   ppl_Pointset_Powerset_C_Polyhedron_t res;
 216   Value v, v_op;
 217   graphite_dim_t i;
 218
 219   value_init (v);
 220   value_init (v_op);
 221   value_set_si (v, 1);
 222   value_set_si (v_op, -1);
 223
 224   ppl_new_C_Polyhedron_from_space_dimension (&subscript_equalities, dim, 0);
 225   for (i = 0; i < nb_subscripts; i++)
 226     {
 227       ppl_Linear_Expression_t expr;
 228       ppl_Constraint_t cstr;
 229       ppl_Coefficient_t coef;
 230
 231       ppl_new_Coefficient (&coef);
 232       ppl_new_Linear_Expression_with_dimension (&expr, dim);
 233
 234       ppl_assign_Coefficient_from_mpz_t (coef, v);
 235       ppl_Linear_Expression_add_to_coefficient (expr, pos + i, coef);
 236       ppl_assign_Coefficient_from_mpz_t (coef, v_op);
 237       ppl_Linear_Expression_add_to_coefficient (expr, pos + i + nb_subscripts,
 238                                                 coef);
 239
 240       ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
 241       ppl_Polyhedron_add_constraint (subscript_equalities, cstr);
 242
 243       ppl_delete_Linear_Expression (expr);
 244       ppl_delete_Constraint (cstr);
 245       ppl_delete_Coefficient (coef);
 246     }
 247
 248   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
 249     (&res, subscript_equalities);
 250   value_clear (v);
 251   value_clear (v_op);
 252   ppl_delete_Polyhedron (subscript_equalities);
 253
 254   return res;
 255 }
 256
 257 /* Builds scheduling equality constraints.  */
 258
 259 static ppl_Pointset_Powerset_C_Polyhedron_t
 260 build_pairwise_scheduling_equality (graphite_dim_t dim,
 261                                     graphite_dim_t pos, graphite_dim_t offset)
 262 {
 263   ppl_Pointset_Powerset_C_Polyhedron_t res;
 264   ppl_Polyhedron_t equalities;
 265   ppl_Constraint_t cstr;
 266
 267   ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
 268
 269   cstr = build_pairwise_constraint (dim, pos, pos + offset, 0,
 270                                     PPL_CONSTRAINT_TYPE_EQUAL);
 271   ppl_Polyhedron_add_constraint (equalities, cstr);
 272   ppl_delete_Constraint (cstr);
 273
 274   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
 275   ppl_delete_Polyhedron (equalities);
 276   return res;
 277 }
 278
 279 /* Builds scheduling inequality constraints.  */
 280
 281 static ppl_Pointset_Powerset_C_Polyhedron_t
 282 build_pairwise_scheduling_inequality (graphite_dim_t dim,
 283                                       graphite_dim_t pos,
 284                                       graphite_dim_t offset,
 285                                       bool direction)
 286 {
 287   ppl_Pointset_Powerset_C_Polyhedron_t res;
 288   ppl_Polyhedron_t equalities;
 289   ppl_Constraint_t cstr;
 290
 291   ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
 292
 293   if (direction)
 294     cstr = build_pairwise_constraint (dim, pos, pos + offset, -1,
 295                                       PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 296   else
 297     cstr = build_pairwise_constraint (dim, pos, pos + offset, 1,
 298                                       PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
 299
 300   ppl_Polyhedron_add_constraint (equalities, cstr);
 301   ppl_delete_Constraint (cstr);
 302
 303   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
 304   ppl_delete_Polyhedron (equalities);
 305   return res;
 306 }
 307
 308 /* Returns true when adding the lexicographical constraints at level I
 309    to the RES dependence polyhedron returns an empty polyhedron.  */
 310
 311 static bool
 312 lexicographically_gt_p (ppl_Pointset_Powerset_C_Polyhedron_t res,
 313                         graphite_dim_t dim,
 314                         graphite_dim_t offset,
 315                         bool direction, graphite_dim_t i)
 316 {
 317   ppl_Pointset_Powerset_C_Polyhedron_t ineq;
 318   bool empty_p;
 319
 320   ineq = build_pairwise_scheduling_inequality (dim, i, offset,
 321                                                direction);
 322   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq, res);
 323   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq);
 324   if (!empty_p)
 325     ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, ineq);
 326   ppl_delete_Pointset_Powerset_C_Polyhedron (ineq);
 327
 328   return !empty_p;
 329 }
 330
 331 /* Build the precedence constraints for the lexicographical comparison
 332    of time vectors RES following the lexicographical order.  */
 333
 334 static void
 335 build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t *res,
 336                                        graphite_dim_t dim,
 337                                        graphite_dim_t tdim1,
 338                                        graphite_dim_t offset,
 339                                        bool direction)
 340 {
 341   graphite_dim_t i;
 342
 343   if (lexicographically_gt_p (*res, dim, offset, direction, 0))
 344     return;
 345
 346   for (i = 0; i < tdim1 - 1; i++)
 347     {
 348       ppl_Pointset_Powerset_C_Polyhedron_t sceq;
 349
 350       sceq = build_pairwise_scheduling_equality (dim, i, offset);
 351       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, sceq);
 352       ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
 353
 354       if (lexicographically_gt_p (*res, dim, offset, direction, i + 1))
 355         return;
 356     }
 357
 358   if (i == tdim1 - 1)
 359     {
 360       ppl_delete_Pointset_Powerset_C_Polyhedron (*res);
 361       ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res, dim, 1);
 362     }
 363 }
 364
 365 /* Build the dependence polyhedron for data references PDR1 and PDR2.  */
 366
 367 static ppl_Pointset_Powerset_C_Polyhedron_t
 368 dependence_polyhedron_1 (poly_bb_p pbb1, poly_bb_p pbb2,
 369                          ppl_Pointset_Powerset_C_Polyhedron_t d1,
 370                          ppl_Pointset_Powerset_C_Polyhedron_t d2,
 371                          poly_dr_p pdr1, poly_dr_p pdr2,
 372                          ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
 373                          bool direction,
 374                          bool original_scattering_p)
 375 {
 376   scop_p scop = PBB_SCOP (pbb1);
 377   graphite_dim_t tdim1 = original_scattering_p ?
 378     pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
 379   graphite_dim_t tdim2 = original_scattering_p ?
 380     pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
 381   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 382   graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
 383   graphite_dim_t sdim1 = pdr_nb_subscripts (pdr1) + 1;
 384   graphite_dim_t gdim = scop_nb_params (scop);
 385   graphite_dim_t dim1 = pdr_dim (pdr1);
 386   graphite_dim_t dim2 = pdr_dim (pdr2);
 387   graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2;
 388   ppl_Pointset_Powerset_C_Polyhedron_t res;
 389   ppl_Pointset_Powerset_C_Polyhedron_t id1, id2, isc1, isc2, idr1, idr2;
 390   ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
 391
 392   gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
 393   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, s1);
 394   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, s2);
 395
 396   id1 = map_into_dep_poly (dim, gdim, d1, ddim1, tdim1);
 397   id2 = map_into_dep_poly (dim, gdim, d2, ddim2, tdim1 + ddim1 + tdim2);
 398   isc1 = map_into_dep_poly (dim, gdim, sc1, ddim1 + tdim1, 0);
 399   isc2 = map_into_dep_poly (dim, gdim, sc2, ddim2 + tdim2, tdim1 + ddim1);
 400
 401   idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
 402                                tdim1, tdim2 + ddim2);
 403   idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
 404                                tdim1 + ddim1 + tdim2, sdim1);
 405
 406   /* Now add the subscript equalities.  */
 407   dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
 408
 409   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
 410   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id1);
 411   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id2);
 412   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc1);
 413   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc2);
 414   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1);
 415   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
 416   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq);
 417   ppl_delete_Pointset_Powerset_C_Polyhedron (id1);
 418   ppl_delete_Pointset_Powerset_C_Polyhedron (id2);
 419   ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
 420   ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
 421   ppl_delete_Pointset_Powerset_C_Polyhedron (isc1);
 422   ppl_delete_Pointset_Powerset_C_Polyhedron (isc2);
 423   ppl_delete_Pointset_Powerset_C_Polyhedron (idr1);
 424   ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
 425   ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
 426
 427   if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
 428     build_lexicographically_gt_constraint (&res, dim, MIN (tdim1, tdim2),
 429                                            tdim1 + ddim1, direction);
 430   return res;
 431 }
 432
 433 /* Build the dependence polyhedron for data references PDR1 and PDR2.
 434    If possible use already cached information.  */
 435
 436 static ppl_Pointset_Powerset_C_Polyhedron_t
 437 dependence_polyhedron (poly_bb_p pbb1, poly_bb_p pbb2,
 438                        ppl_Pointset_Powerset_C_Polyhedron_t d1,
 439                        ppl_Pointset_Powerset_C_Polyhedron_t d2,
 440                        poly_dr_p pdr1, poly_dr_p pdr2,
 441                        ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
 442                        bool direction,
 443                        bool original_scattering_p)
 444 {
 445   poly_dr_pair tmp;
 446   PTR *x = NULL;
 447   ppl_Pointset_Powerset_C_Polyhedron_t res;
 448
 449   if (original_scattering_p)
 450     {
 451       tmp.source = pdr1;
 452       tmp.sink = pdr2;
 453       x = htab_find_slot (SCOP_ORIGINAL_PDR_PAIRS (PBB_SCOP (pbb1)),
 454                           &tmp, INSERT);
 455
 456       if (x && *x)
 457         {
 458           if (dump_file && (dump_flags & TDF_DETAILS))
 459             fprintf (dump_file, "\nddp cache: hit.\n");
 460           return ((poly_dr_pair *)*x)->ddp;
 461         }
 462       else if (dump_file && (dump_flags & TDF_DETAILS))
 463         fprintf (dump_file, "\nddp cache: miss.\n");
 464     }
 465
 466   res = dependence_polyhedron_1 (pbb1, pbb2, d1, d2, pdr1, pdr2,
 467                                  s1, s2, direction, original_scattering_p);
 468
 469   if (original_scattering_p)
 470     {
 471       gcc_assert (x && *x == NULL);
 472       *x = new_poly_dr_pair (pdr1, pdr2, res);
 473
 474       if (dump_file && (dump_flags & TDF_DETAILS))
 475         fprintf (dump_file, "\nddp cache: add element.\n");
 476     }
 477
 478   return res;
 479 }
 480
 481 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
 482    and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
 483    functions.  */
 484
 485 static bool
 486 graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
 487                              poly_dr_p pdr1, poly_dr_p pdr2)
 488 {
 489   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 490   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 491   ppl_Polyhedron_t so1 = PBB_ORIGINAL_SCATTERING (pbb1);
 492   ppl_Polyhedron_t so2 = PBB_ORIGINAL_SCATTERING (pbb2);
 493   ppl_Pointset_Powerset_C_Polyhedron_t po;
 494
 495   graphite_dim_t sdim1 = pdr_nb_subscripts (pdr1) + 1;
 496   graphite_dim_t sdim2 = pdr_nb_subscripts (pdr2) + 1;
 497
 498   if (sdim1 != sdim2)
 499     return true;
 500
 501   po = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
 502                               true, true);
 503
 504   if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (po))
 505     return true;
 506   else
 507     {
 508       ppl_Polyhedron_t st1 = PBB_TRANSFORMED_SCATTERING (pbb1);
 509       ppl_Polyhedron_t st2 = PBB_TRANSFORMED_SCATTERING (pbb2);
 510       ppl_Pointset_Powerset_C_Polyhedron_t pt;
 511       graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 512       graphite_dim_t otdim1 = pbb_nb_scattering_orig (pbb1);
 513       graphite_dim_t otdim2 = pbb_nb_scattering_orig (pbb2);
 514       graphite_dim_t ttdim1 = pbb_nb_scattering_transform (pbb1);
 515       graphite_dim_t ttdim2 = pbb_nb_scattering_transform (pbb2);
 516
 517       if (dump_file && (dump_flags & TDF_DETAILS))
 518         fprintf (dump_file, "\nloop carries dependency.\n");
 519       pt = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
 520                                   false, false);
 521
 522       /* Extend PO and PT to have the same dimensions.  */
 523       ppl_insert_dimensions_pointset (po, otdim1, ttdim1);
 524       ppl_insert_dimensions_pointset (po, otdim1 + ttdim1 + ddim1 + otdim2,
 525                                       ttdim2);
 526       ppl_insert_dimensions_pointset (pt, 0, otdim1);
 527       ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
 528
 529       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po, pt);
 530       return ppl_Pointset_Powerset_C_Polyhedron_is_empty (po);
 531     }
 532 }
 533
 534 /* Iterates over the data references of PBB1 and PBB2 and detect
 535    whether the transformed schedule is correct.  */
 536
 537 static bool
 538 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
 539 {
 540   int i, j;
 541   poly_dr_p pdr1, pdr2;
 542
 543   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 544     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 545       if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
 546         return false;
 547   return true;
 548 }
 549
 550 /* Iterates over the SCOP and detect whether the transformed schedule
 551    is correct.  */
 552
 553 bool
 554 graphite_legal_transform (scop_p scop)
 555 {
 556   int i, j;
 557   poly_bb_p pbb1, pbb2;
 558
 559   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 560     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 561       if (!graphite_legal_transform_bb (pbb1, pbb2))
 562         return false;
 563
 564   return true;
 565 }
 566
 567 /* Remove all the dimensions except alias information at dimension
 568    ALIAS_DIM.  */
 569
 570 static void
 571 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
 572                           ppl_dimension_type alias_dim)
 573 {
 574   ppl_dimension_type *ds;
 575   ppl_dimension_type access_dim;
 576   unsigned i, pos = 0;
 577
 578   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
 579                                                       &access_dim);
 580   ds = XNEWVEC (ppl_dimension_type, access_dim-1);
 581   for (i = 0; i < access_dim; i++)
 582     {
 583       if (i == alias_dim)
 584         continue;
 585
 586       ds[pos] = i;
 587       pos++;
 588     }
 589
 590   ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
 591                                                               ds,
 592                                                               access_dim - 1);
 593   free (ds);
 594 }
 595
 596 /* Return true when PDR1 and PDR2 may alias.  */
 597
 598 static bool
 599 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
 600 {
 601   ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
 602   ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
 603   ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
 604   ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
 605   ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
 606   int empty_p;
 607
 608   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 609     (&alias_powerset1, accesses1);
 610   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 611     (&alias_powerset2, accesses2);
 612
 613   build_alias_set_powerset (alias_powerset1, alias_dim1);
 614   build_alias_set_powerset (alias_powerset2, alias_dim2);
 615
 616   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
 617     (alias_powerset1, alias_powerset2);
 618
 619   empty_p =  ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
 620
 621   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
 622   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
 623
 624   return !empty_p;
 625 }
 626
 627 /* Returns TRUE when the dependence polyhedron between PDR1 and
 628    PDR2 represents a loop carried dependence at level LEVEL. Otherwise
 629    return FALSE.  */
 630
 631 static bool
 632 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
 633                                      int level)
 634 {
 635   poly_bb_p pbb1 = PDR_PBB (pdr1);
 636   poly_bb_p pbb2 = PDR_PBB (pdr2);
 637   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 638   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 639   ppl_Polyhedron_t so1 = PBB_TRANSFORMED_SCATTERING (pbb1);
 640   ppl_Polyhedron_t so2 = PBB_TRANSFORMED_SCATTERING (pbb2);
 641   ppl_Pointset_Powerset_C_Polyhedron_t po;
 642   ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
 643   graphite_dim_t sdim1 = pdr_nb_subscripts (pdr1) + 1;
 644   graphite_dim_t sdim2 = pdr_nb_subscripts (pdr2) + 1;
 645   graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
 646   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 647   ppl_dimension_type dim;
 648   bool empty_p;
 649
 650   if ((PDR_TYPE (pdr1) == PDR_READ && PDR_TYPE (pdr2) == PDR_READ)
 651       || !poly_drs_may_alias_p (pdr1, pdr2))
 652     return false;
 653
 654   if (sdim1 != sdim2)
 655     return true;
 656
 657   po = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
 658                               true, false);
 659   if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (po))
 660     {
 661       ppl_delete_Pointset_Powerset_C_Polyhedron (po);
 662       return false;
 663     }
 664
 665   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
 666   eqpp = build_pairwise_scheduling_inequality (dim, level, tdim1 + ddim1, 1);
 667
 668   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
 669   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
 670
 671   ppl_delete_Pointset_Powerset_C_Polyhedron (po);
 672   ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
 673   return !empty_p;
 674 }
 675
 676 /* Check data dependency between PBB1 and PBB2 at level LEVEL.  */
 677
 678 bool
 679 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
 680 {
 681   int i, j;
 682   poly_dr_p pdr1, pdr2;
 683
 684   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 685     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 686       if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
 687         return true;
 688
 689   return false;
 690 }
 691
 692 #endif