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       ppl_Pointset_Powerset_C_Polyhedron_t temp;
 517       ppl_dimension_type pdim;
 518       bool is_empty_p;
 519
 520       /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
 521          Keep in mind, that PO polyhedron might be restored from the cache
 522          and should not be modified!  */
 523       ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
 524       ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp,
 525                                                                    pdim, 0);
 526       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, po);
 527
 528       if (dump_file && (dump_flags & TDF_DETAILS))
 529         fprintf (dump_file, "\nloop carries dependency.\n");
 530       pt = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
 531                                   false, false);
 532
 533       /* Extend PO and PT to have the same dimensions.  */
 534       ppl_insert_dimensions_pointset (temp, otdim1, ttdim1);
 535       ppl_insert_dimensions_pointset (temp, otdim1 + ttdim1 + ddim1 + otdim2,
 536                                       ttdim2);
 537       ppl_insert_dimensions_pointset (pt, 0, otdim1);
 538       ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
 539
 540       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, pt);
 541       is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp);
 542
 543       ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
 544       ppl_delete_Pointset_Powerset_C_Polyhedron (pt);
 545       return is_empty_p;
 546     }
 547 }
 548
 549 /* Iterates over the data references of PBB1 and PBB2 and detect
 550    whether the transformed schedule is correct.  */
 551
 552 static bool
 553 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
 554 {
 555   int i, j;
 556   poly_dr_p pdr1, pdr2;
 557
 558   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 559     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 560       if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
 561         return false;
 562   return true;
 563 }
 564
 565 /* Iterates over the SCOP and detect whether the transformed schedule
 566    is correct.  */
 567
 568 bool
 569 graphite_legal_transform (scop_p scop)
 570 {
 571   int i, j;
 572   poly_bb_p pbb1, pbb2;
 573
 574   timevar_push (TV_GRAPHITE_DATA_DEPS);
 575
 576   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 577     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 578       if (!graphite_legal_transform_bb (pbb1, pbb2))
 579         {
 580           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 581           return false;
 582         }
 583
 584   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 585   return true;
 586 }
 587
 588 /* Remove all the dimensions except alias information at dimension
 589    ALIAS_DIM.  */
 590
 591 static void
 592 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
 593                           ppl_dimension_type alias_dim)
 594 {
 595   ppl_dimension_type *ds;
 596   ppl_dimension_type access_dim;
 597   unsigned i, pos = 0;
 598
 599   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
 600                                                       &access_dim);
 601   ds = XNEWVEC (ppl_dimension_type, access_dim-1);
 602   for (i = 0; i < access_dim; i++)
 603     {
 604       if (i == alias_dim)
 605         continue;
 606
 607       ds[pos] = i;
 608       pos++;
 609     }
 610
 611   ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
 612                                                               ds,
 613                                                               access_dim - 1);
 614   free (ds);
 615 }
 616
 617 /* Return true when PDR1 and PDR2 may alias.  */
 618
 619 static bool
 620 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
 621 {
 622   ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
 623   ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
 624   ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
 625   ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
 626   ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
 627   int empty_p;
 628
 629   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 630     (&alias_powerset1, accesses1);
 631   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 632     (&alias_powerset2, accesses2);
 633
 634   build_alias_set_powerset (alias_powerset1, alias_dim1);
 635   build_alias_set_powerset (alias_powerset2, alias_dim2);
 636
 637   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
 638     (alias_powerset1, alias_powerset2);
 639
 640   empty_p =  ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
 641
 642   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
 643   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
 644
 645   return !empty_p;
 646 }
 647
 648 /* Returns TRUE when the dependence polyhedron between PDR1 and
 649    PDR2 represents a loop carried dependence at level LEVEL. Otherwise
 650    return FALSE.  */
 651
 652 static bool
 653 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
 654                                      int level)
 655 {
 656   poly_bb_p pbb1 = PDR_PBB (pdr1);
 657   poly_bb_p pbb2 = PDR_PBB (pdr2);
 658   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 659   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 660   ppl_Polyhedron_t so1 = PBB_TRANSFORMED_SCATTERING (pbb1);
 661   ppl_Polyhedron_t so2 = PBB_TRANSFORMED_SCATTERING (pbb2);
 662   ppl_Pointset_Powerset_C_Polyhedron_t po;
 663   ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
 664   graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
 665   graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
 666   graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
 667   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 668   ppl_dimension_type dim;
 669   bool empty_p;
 670
 671   if ((PDR_TYPE (pdr1) == PDR_READ && PDR_TYPE (pdr2) == PDR_READ)
 672       || !poly_drs_may_alias_p (pdr1, pdr2))
 673     return false;
 674
 675   if (sdim1 != sdim2)
 676     return true;
 677
 678   po = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
 679                               true, false);
 680   if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (po))
 681     {
 682       ppl_delete_Pointset_Powerset_C_Polyhedron (po);
 683       return false;
 684     }
 685
 686   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
 687   eqpp = build_pairwise_scheduling_inequality (dim, level, tdim1 + ddim1, 1);
 688
 689   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
 690   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
 691
 692   ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
 693   return !empty_p;
 694 }
 695
 696 /* Check data dependency between PBB1 and PBB2 at level LEVEL.  */
 697
 698 bool
 699 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
 700 {
 701   int i, j;
 702   poly_dr_p pdr1, pdr2;
 703
 704   timevar_push (TV_GRAPHITE_DATA_DEPS);
 705
 706   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 707     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 708       if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
 709         {
 710           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 711           return true;
 712         }
 713
 714   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 715   return false;
 716 }
 717
 718 #endif