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 OFFSET0
 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
 393 static poly_ddr_p
 394 dependence_polyhedron_1 (poly_bb_p pbb1, poly_bb_p pbb2,
 395                          ppl_Pointset_Powerset_C_Polyhedron_t d1,
 396                          ppl_Pointset_Powerset_C_Polyhedron_t d2,
 397                          poly_dr_p pdr1, poly_dr_p pdr2,
 398                          ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
 399                          bool direction,
 400                          bool original_scattering_p)
 401 {
 402   scop_p scop = PBB_SCOP (pbb1);
 403   graphite_dim_t tdim1 = original_scattering_p ?
 404     pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
 405   graphite_dim_t tdim2 = original_scattering_p ?
 406     pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
 407   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 408   graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
 409   graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
 410   graphite_dim_t gdim = scop_nb_params (scop);
 411   graphite_dim_t dim1 = pdr_dim (pdr1);
 412   graphite_dim_t dim2 = pdr_dim (pdr2);
 413   graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2;
 414   ppl_Pointset_Powerset_C_Polyhedron_t res;
 415   ppl_Pointset_Powerset_C_Polyhedron_t id1, id2, isc1, isc2, idr1, idr2;
 416   ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
 417
 418   gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
 419   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, s1);
 420   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, s2);
 421
 422   id1 = map_into_dep_poly (dim, gdim, d1, ddim1, tdim1);
 423   id2 = map_into_dep_poly (dim, gdim, d2, ddim2, tdim1 + ddim1 + tdim2);
 424   isc1 = map_into_dep_poly (dim, gdim, sc1, ddim1 + tdim1, 0);
 425   isc2 = map_into_dep_poly (dim, gdim, sc2, ddim2 + tdim2, tdim1 + ddim1);
 426
 427   idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
 428                                tdim1, tdim2 + ddim2);
 429   idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
 430                                tdim1 + ddim1 + tdim2, sdim1);
 431
 432   /* Now add the subscript equalities.  */
 433   dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
 434
 435   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
 436   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id1);
 437   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id2);
 438   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc1);
 439   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc2);
 440   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1);
 441   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
 442   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq);
 443   ppl_delete_Pointset_Powerset_C_Polyhedron (id1);
 444   ppl_delete_Pointset_Powerset_C_Polyhedron (id2);
 445   ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
 446   ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
 447   ppl_delete_Pointset_Powerset_C_Polyhedron (isc1);
 448   ppl_delete_Pointset_Powerset_C_Polyhedron (isc2);
 449   ppl_delete_Pointset_Powerset_C_Polyhedron (idr1);
 450   ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
 451   ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
 452
 453   if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
 454     build_lexicographically_gt_constraint (&res, dim, MIN (tdim1, tdim2),
 455                                            tdim1 + ddim1, direction);
 456
 457   return new_poly_ddr (pdr1, pdr2, res);
 458 }
 459
 460 /* Build the dependence polyhedron for data references PDR1 and PDR2.
 461    If possible use already cached information.  */
 462
 463 static poly_ddr_p
 464 dependence_polyhedron (poly_bb_p pbb1, poly_bb_p pbb2,
 465                        ppl_Pointset_Powerset_C_Polyhedron_t d1,
 466                        ppl_Pointset_Powerset_C_Polyhedron_t d2,
 467                        poly_dr_p pdr1, poly_dr_p pdr2,
 468                        ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
 469                        bool direction,
 470                        bool original_scattering_p)
 471 {
 472   PTR *x = NULL;
 473   poly_ddr_p res;
 474
 475   if (original_scattering_p)
 476     {
 477       struct poly_ddr tmp;
 478
 479       tmp.source = pdr1;
 480       tmp.sink = pdr2;
 481       x = htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1)),
 482                           &tmp, INSERT);
 483
 484       if (x && *x)
 485         return (poly_ddr_p) *x;
 486     }
 487
 488   res = dependence_polyhedron_1 (pbb1, pbb2, d1, d2, pdr1, pdr2,
 489                                  s1, s2, direction, original_scattering_p);
 490
 491   if (original_scattering_p)
 492     *x = res;
 493
 494   return res;
 495 }
 496
 497 static bool
 498 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2);
 499
 500 /* Returns the PDDR corresponding to the original schedule, or NULL if
 501    the dependence relation is empty or unknown (Can't judge dependency
 502    under polyhedral model.  */
 503
 504 static poly_ddr_p
 505 pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
 506                           poly_dr_p pdr1, poly_dr_p pdr2)
 507 {
 508   poly_ddr_p pddr;
 509   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 510   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 511   ppl_Polyhedron_t so1 = PBB_ORIGINAL_SCATTERING (pbb1);
 512   ppl_Polyhedron_t so2 = PBB_ORIGINAL_SCATTERING (pbb2);
 513
 514   if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
 515       || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
 516       || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
 517     return NULL;
 518
 519   pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
 520                                 true, true);
 521   if (pddr_is_empty (pddr))
 522     return NULL;
 523
 524   return pddr;
 525 }
 526
 527 /* Return true when the data dependence relation between the data
 528    references PDR1 belonging to PBB1 and PDR2 is part of a
 529    reduction.  */
 530
 531 static inline bool
 532 reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
 533 {
 534   int i;
 535   poly_dr_p pdr;
 536
 537   /* PBB1 should be a reduction PBB.  Reduction PBBs should have only
 538      one write.  */
 539   gcc_assert (PBB_IS_REDUCTION (pbb1)
 540               && number_of_write_pdrs (pbb1) == 1);
 541
 542   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
 543     if (PDR_TYPE (pdr) == PDR_WRITE)
 544       break;
 545
 546   return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
 547 }
 548
 549 /* Return true when the data dependence relation between the data
 550    references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
 551    part of a reduction.  */
 552
 553 static inline bool
 554 reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2,
 555                 poly_dr_p pdr1, poly_dr_p pdr2)
 556 {
 557   if (PBB_IS_REDUCTION (pbb1))
 558     return reduction_dr_1 (pbb1, pdr1, pdr2);
 559
 560   if (PBB_IS_REDUCTION (pbb2))
 561     return reduction_dr_1 (pbb2, pdr2, pdr1);
 562
 563   return false;
 564 }
 565
 566 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
 567    and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
 568    functions.  */
 569
 570 static bool
 571 graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
 572                              poly_dr_p pdr1, poly_dr_p pdr2)
 573 {
 574   ppl_Polyhedron_t st1, st2;
 575   ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
 576   graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
 577   ppl_Pointset_Powerset_C_Polyhedron_t temp;
 578   ppl_dimension_type pdim;
 579   bool is_empty_p;
 580   poly_ddr_p pddr;
 581   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 582   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 583
 584   if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
 585     return true;
 586
 587   pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2);
 588   if (!pddr)
 589     return true;
 590
 591   po = PDDR_DDP (pddr);
 592
 593   if (dump_file && (dump_flags & TDF_DETAILS))
 594     fprintf (dump_file, "\nloop carries dependency.\n");
 595
 596   st1 = PBB_TRANSFORMED_SCATTERING (pbb1);
 597   st2 = PBB_TRANSFORMED_SCATTERING (pbb2);
 598   ddim1 = pbb_dim_iter_domain (pbb1);
 599   otdim1 = pbb_nb_scattering_orig (pbb1);
 600   otdim2 = pbb_nb_scattering_orig (pbb2);
 601   ttdim1 = pbb_nb_scattering_transform (pbb1);
 602   ttdim2 = pbb_nb_scattering_transform (pbb2);
 603
 604   /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
 605      Keep in mind, that PO polyhedron might be restored from the cache
 606      and should not be modified!  */
 607   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
 608   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp, pdim, 0);
 609   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, po);
 610
 611   pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
 612                                 false, false);
 613   pt = PDDR_DDP (pddr);
 614
 615   /* Extend PO and PT to have the same dimensions.  */
 616   ppl_insert_dimensions_pointset (temp, otdim1, ttdim1);
 617   ppl_insert_dimensions_pointset (temp, otdim1 + ttdim1 + ddim1 + otdim2, ttdim2);
 618   ppl_insert_dimensions_pointset (pt, 0, otdim1);
 619   ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
 620
 621   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, pt);
 622   is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp);
 623
 624   ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
 625   free_poly_ddr (pddr);
 626
 627   return is_empty_p;
 628 }
 629
 630 /* Return true when the data dependence relation for PBB1 and PBB2 is
 631    part of a reduction.  */
 632
 633 static inline bool
 634 reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
 635 {
 636   return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
 637 }
 638
 639 /* Iterates over the data references of PBB1 and PBB2 and detect
 640    whether the transformed schedule is correct.  */
 641
 642 static bool
 643 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
 644 {
 645   int i, j;
 646   poly_dr_p pdr1, pdr2;
 647
 648   if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
 649     pbb_remove_duplicate_pdrs (pbb1);
 650
 651   if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
 652     pbb_remove_duplicate_pdrs (pbb2);
 653
 654   if (reduction_ddr_p (pbb1, pbb2))
 655     return true;
 656
 657   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 658     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 659       if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
 660         return false;
 661
 662   return true;
 663 }
 664
 665 /* Iterates over the SCOP and detect whether the transformed schedule
 666    is correct.  */
 667
 668 bool
 669 graphite_legal_transform (scop_p scop)
 670 {
 671   int i, j;
 672   poly_bb_p pbb1, pbb2;
 673
 674   timevar_push (TV_GRAPHITE_DATA_DEPS);
 675
 676   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 677     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 678       if (!graphite_legal_transform_bb (pbb1, pbb2))
 679         {
 680           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 681           return false;
 682         }
 683
 684   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 685   return true;
 686 }
 687
 688 /* Remove all the dimensions except alias information at dimension
 689    ALIAS_DIM.  */
 690
 691 static void
 692 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
 693                           ppl_dimension_type alias_dim)
 694 {
 695   ppl_dimension_type *ds;
 696   ppl_dimension_type access_dim;
 697   unsigned i, pos = 0;
 698
 699   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
 700                                                       &access_dim);
 701   ds = XNEWVEC (ppl_dimension_type, access_dim-1);
 702   for (i = 0; i < access_dim; i++)
 703     {
 704       if (i == alias_dim)
 705         continue;
 706
 707       ds[pos] = i;
 708       pos++;
 709     }
 710
 711   ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
 712                                                               ds,
 713                                                               access_dim - 1);
 714   free (ds);
 715 }
 716
 717 /* Return true when PDR1 and PDR2 may alias.  */
 718
 719 static bool
 720 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
 721 {
 722   ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
 723   ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
 724   ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
 725   ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
 726   ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
 727   int empty_p;
 728
 729   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 730     (&alias_powerset1, accesses1);
 731   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 732     (&alias_powerset2, accesses2);
 733
 734   build_alias_set_powerset (alias_powerset1, alias_dim1);
 735   build_alias_set_powerset (alias_powerset2, alias_dim2);
 736
 737   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
 738     (alias_powerset1, alias_powerset2);
 739
 740   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
 741
 742   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
 743   ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
 744
 745   return !empty_p;
 746 }
 747
 748 /* Returns TRUE when the dependence polyhedron between PDR1 and
 749    PDR2 represents a loop carried dependence at level LEVEL.  */
 750
 751 static bool
 752 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
 753                                      int level)
 754 {
 755   poly_bb_p pbb1 = PDR_PBB (pdr1);
 756   poly_bb_p pbb2 = PDR_PBB (pdr2);
 757   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
 758   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 759   ppl_Polyhedron_t so1 = PBB_TRANSFORMED_SCATTERING (pbb1);
 760   ppl_Polyhedron_t so2 = PBB_TRANSFORMED_SCATTERING (pbb2);
 761   ppl_Pointset_Powerset_C_Polyhedron_t po;
 762   ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
 763   graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
 764   graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
 765   ppl_dimension_type dim;
 766   bool empty_p;
 767   poly_ddr_p pddr;
 768   int obj_base_set1 = PDR_BASE_OBJECT_SET (pdr1);
 769   int obj_base_set2 = PDR_BASE_OBJECT_SET (pdr2);
 770
 771   if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
 772       || !poly_drs_may_alias_p (pdr1, pdr2))
 773     return false;
 774
 775   if (obj_base_set1 != obj_base_set2)
 776     return true;
 777
 778   if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
 779     return false;
 780
 781   pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
 782                                 true, false);
 783
 784   if (pddr_is_empty (pddr))
 785     return false;
 786
 787   po = PDDR_DDP (pddr);
 788   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
 789   eqpp = build_pairwise_scheduling_inequality (dim, level, tdim1 + ddim1, 1);
 790
 791   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
 792   empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
 793
 794   ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
 795   return !empty_p;
 796 }
 797
 798 /* Check data dependency between PBB1 and PBB2 at level LEVEL.  */
 799
 800 bool
 801 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
 802 {
 803   int i, j;
 804   poly_dr_p pdr1, pdr2;
 805
 806   timevar_push (TV_GRAPHITE_DATA_DEPS);
 807
 808   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
 809     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
 810       if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
 811         {
 812           timevar_pop (TV_GRAPHITE_DATA_DEPS);
 813           return true;
 814         }
 815
 816   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 817   return false;
 818 }
 819
 820 /* Pretty print to FILE all the data dependences of SCoP in DOT
 821    format.  */
 822
 823 static void
 824 dot_deps_stmt_1 (FILE *file, scop_p scop)
 825 {
 826   int i, j, k, l;
 827   poly_bb_p pbb1, pbb2;
 828   poly_dr_p pdr1, pdr2;
 829
 830   fputs ("digraph all {\n", file);
 831
 832   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 833     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 834       {
 835         for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 836           for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 837             if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2))
 838               {
 839                 fprintf (file, "S%d -> S%d\n",
 840                          pbb_index (pbb1), pbb_index (pbb2));
 841                 goto done;
 842               }
 843       done:;
 844       }
 845
 846   fputs ("}\n\n", file);
 847 }
 848
 849 /* Pretty print to FILE all the data dependences of SCoP in DOT
 850    format.  */
 851
 852 static void
 853 dot_deps_1 (FILE *file, scop_p scop)
 854 {
 855   int i, j, k, l;
 856   poly_bb_p pbb1, pbb2;
 857   poly_dr_p pdr1, pdr2;
 858
 859   fputs ("digraph all {\n", file);
 860
 861   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
 862     for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
 863       for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
 864         for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
 865           if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2))
 866             fprintf (file, "S%d_D%d -> S%d_D%d\n",
 867                      pbb_index (pbb1), PDR_ID (pdr1),
 868                      pbb_index (pbb2), PDR_ID (pdr2));
 869
 870   fputs ("}\n\n", file);
 871 }
 872
 873 /* Display all the data dependences in SCoP using dotty.  */
 874
 875 void
 876 dot_deps (scop_p scop)
 877 {
 878   /* When debugging, enable the following code.  This cannot be used
 879      in production compilers because it calls "system".  */
 880 #if 0
 881   int x;
 882   FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
 883   gcc_assert (stream);
 884
 885   dot_deps_1 (stream, scop);
 886   fclose (stream);
 887
 888   x = system ("dotty /tmp/scopdeps.dot");
 889 #else
 890   dot_deps_1 (stderr, scop);
 891 #endif
 892 }
 893
 894 /* Display all the statement dependences in SCoP using dotty.  */
 895
 896 void
 897 dot_deps_stmt (scop_p scop)
 898 {
 899   /* When debugging, enable the following code.  This cannot be used
 900      in production compilers because it calls "system".  */
 901 #if 0
 902   int x;
 903   FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
 904   gcc_assert (stream);
 905
 906   dot_deps_stmt_1 (stream, scop);
 907   fclose (stream);
 908
 909   x = system ("dotty /tmp/scopdeps.dot");
 910 #else
 911   dot_deps_stmt_1 (stderr, scop);
 912 #endif
 913 }
 914
 915 #endif