gcc/graphite-dependences.c

   1 /* Data dependence analysis for Graphite.
   2    Copyright (C) 2009-2014 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
  24 #ifdef HAVE_cloog
  25 #include <isl/set.h>
  26 #include <isl/map.h>
  27 #include <isl/union_map.h>
  28 #include <isl/flow.h>
  29 #include <isl/constraint.h>
  30 #include <cloog/cloog.h>
  31 #include <cloog/isl/domain.h>
  32 #endif
  33
  34 #include "system.h"
  35 #include "coretypes.h"
  36 #include "tree.h"
  37 #include "basic-block.h"
  38 #include "tree-ssa-alias.h"
  39 #include "internal-fn.h"
  40 #include "gimple-expr.h"
  41 #include "is-a.h"
  42 #include "gimple.h"
  43 #include "gimple-iterator.h"
  44 #include "tree-ssa-loop.h"
  45 #include "tree-pass.h"
  46 #include "cfgloop.h"
  47 #include "tree-chrec.h"
  48 #include "tree-data-ref.h"
  49 #include "tree-scalar-evolution.h"
  50 #include "sese.h"
  51
  52 #ifdef HAVE_cloog
  53 #include "graphite-poly.h"
  54 #include "graphite-htab.h"
  55
  56 isl_union_map *
  57 scop_get_dependences (scop_p scop)
  58 {
  59   isl_union_map *dependences;
  60
  61   if (!scop->must_raw)
  62     compute_deps (scop, SCOP_BBS (scop),
  63                   &scop->must_raw, &scop->may_raw,
  64                   &scop->must_raw_no_source, &scop->may_raw_no_source,
  65                   &scop->must_war, &scop->may_war,
  66                   &scop->must_war_no_source, &scop->may_war_no_source,
  67                   &scop->must_waw, &scop->may_waw,
  68                   &scop->must_waw_no_source, &scop->may_waw_no_source);
  69
  70   dependences = isl_union_map_copy (scop->must_raw);
  71   dependences = isl_union_map_union (dependences,
  72                                      isl_union_map_copy (scop->must_war));
  73   dependences = isl_union_map_union (dependences,
  74                                      isl_union_map_copy (scop->must_waw));
  75   dependences = isl_union_map_union (dependences,
  76                                      isl_union_map_copy (scop->may_raw));
  77   dependences = isl_union_map_union (dependences,
  78                                      isl_union_map_copy (scop->may_war));
  79   dependences = isl_union_map_union (dependences,
  80                                      isl_union_map_copy (scop->may_waw));
  81
  82   return dependences;
  83 }
  84
  85 /* Add the constraints from the set S to the domain of MAP.  */
  86
  87 static isl_map *
  88 constrain_domain (isl_map *map, isl_set *s)
  89 {
  90   isl_space *d = isl_map_get_space (map);
  91   isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
  92
  93   s = isl_set_set_tuple_id (s, id);
  94   isl_space_free (d);
  95   return isl_map_intersect_domain (map, s);
  96 }
  97
  98 /* Constrain pdr->accesses with pdr->extent and pbb->domain.  */
  99
 100 static isl_map *
 101 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
 102 {
 103   isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
 104                                         isl_set_copy (pdr->extent));
 105   x = constrain_domain (x, isl_set_copy (pbb->domain));
 106   return x;
 107 }
 108
 109 /* Returns all the memory reads in SCOP.  */
 110
 111 static isl_union_map *
 112 scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
 113 {
 114   int i, j;
 115   poly_bb_p pbb;
 116   poly_dr_p pdr;
 117   isl_space *space = isl_set_get_space (scop->context);
 118   isl_union_map *res = isl_union_map_empty (space);
 119
 120   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 121     {
 122       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 123         if (pdr_read_p (pdr))
 124           res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
 125     }
 126
 127   return res;
 128 }
 129
 130 /* Returns all the memory must writes in SCOP.  */
 131
 132 static isl_union_map *
 133 scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
 134 {
 135   int i, j;
 136   poly_bb_p pbb;
 137   poly_dr_p pdr;
 138   isl_space *space = isl_set_get_space (scop->context);
 139   isl_union_map *res = isl_union_map_empty (space);
 140
 141   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 142     {
 143       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 144         if (pdr_write_p (pdr))
 145           res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
 146     }
 147
 148   return res;
 149 }
 150
 151 /* Returns all the memory may writes in SCOP.  */
 152
 153 static isl_union_map *
 154 scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
 155 {
 156   int i, j;
 157   poly_bb_p pbb;
 158   poly_dr_p pdr;
 159   isl_space *space = isl_set_get_space (scop->context);
 160   isl_union_map *res = isl_union_map_empty (space);
 161
 162   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 163     {
 164       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 165         if (pdr_may_write_p (pdr))
 166           res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
 167     }
 168
 169   return res;
 170 }
 171
 172 /* Returns all the original schedules in SCOP.  */
 173
 174 static isl_union_map *
 175 scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
 176 {
 177   int i;
 178   poly_bb_p pbb;
 179   isl_space *space = isl_set_get_space (scop->context);
 180   isl_union_map *res = isl_union_map_empty (space);
 181
 182   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 183     {
 184       res = isl_union_map_add_map
 185         (res, constrain_domain (isl_map_copy (pbb->schedule),
 186                                 isl_set_copy (pbb->domain)));
 187     }
 188
 189   return res;
 190 }
 191
 192 /* Returns all the transformed schedules in SCOP.  */
 193
 194 static isl_union_map *
 195 scop_get_transformed_schedule (scop_p scop, vec<poly_bb_p> pbbs)
 196 {
 197   int i;
 198   poly_bb_p pbb;
 199   isl_space *space = isl_set_get_space (scop->context);
 200   isl_union_map *res = isl_union_map_empty (space);
 201
 202   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 203     {
 204       res = isl_union_map_add_map
 205         (res, constrain_domain (isl_map_copy (pbb->transformed),
 206                                 isl_set_copy (pbb->domain)));
 207     }
 208
 209   return res;
 210 }
 211
 212 /* Helper function used on each MAP of a isl_union_map.  Computes the
 213    maximal output dimension.  */
 214
 215 static int
 216 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
 217 {
 218   int global_max = *((int *) user);
 219   isl_space *space = isl_map_get_space (map);
 220   int nb_out = isl_space_dim (space, isl_dim_out);
 221
 222   if (global_max < nb_out)
 223     *((int *) user) = nb_out;
 224
 225   isl_map_free (map);
 226   isl_space_free (space);
 227   return 0;
 228 }
 229
 230 /* Extends the output dimension of MAP to MAX dimensions.  */
 231
 232 static __isl_give isl_map *
 233 extend_map (__isl_take isl_map *map, int max)
 234 {
 235   isl_space *space = isl_map_get_space (map);
 236   int n = isl_space_dim (space, isl_dim_out);
 237
 238   isl_space_free (space);
 239   return isl_map_add_dims (map, isl_dim_out, max - n);
 240 }
 241
 242 /* Structure used to pass parameters to extend_schedule_1.  */
 243
 244 struct extend_schedule_str {
 245   int max;
 246   isl_union_map *umap;
 247 };
 248
 249 /* Helper function for extend_schedule.  */
 250
 251 static int
 252 extend_schedule_1 (__isl_take isl_map *map, void *user)
 253 {
 254   struct extend_schedule_str *str = (struct extend_schedule_str *) user;
 255   str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
 256   return 0;
 257 }
 258
 259 /* Return a relation that has uniform output dimensions.  */
 260
 261 __isl_give isl_union_map *
 262 extend_schedule (__isl_take isl_union_map *x)
 263 {
 264   int max = 0;
 265   int res;
 266   struct extend_schedule_str str;
 267
 268   res = isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
 269   gcc_assert (res == 0);
 270
 271   str.max = max;
 272   str.umap = isl_union_map_empty (isl_union_map_get_space (x));
 273   res = isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
 274   gcc_assert (res == 0);
 275
 276   isl_union_map_free (x);
 277   return str.umap;
 278 }
 279
 280 /* Applies SCHEDULE to the in and out dimensions of the dependences
 281    DEPS and return the resulting relation.  */
 282
 283 static isl_map *
 284 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
 285                         __isl_keep isl_union_map *deps)
 286 {
 287   isl_map *x;
 288   isl_union_map *ux, *trans;
 289
 290   trans = isl_union_map_copy (schedule);
 291   trans = extend_schedule (trans);
 292   ux = isl_union_map_copy (deps);
 293   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
 294   ux = isl_union_map_apply_range (ux, trans);
 295   if (isl_union_map_is_empty (ux))
 296     {
 297       isl_union_map_free (ux);
 298       return NULL;
 299     }
 300   x = isl_map_from_union_map (ux);
 301
 302   return x;
 303 }
 304
 305 /* Return true when SCHEDULE does not violate the data DEPS: that is
 306    when the intersection of LEX with the DEPS transformed by SCHEDULE
 307    is empty.  LEX is the relation in which the outputs occur before
 308    the inputs.  */
 309
 310 static bool
 311 no_violations (__isl_keep isl_union_map *schedule,
 312                __isl_keep isl_union_map *deps)
 313 {
 314   bool res;
 315   isl_space *space;
 316   isl_map *lex, *x;
 317
 318   if (isl_union_map_is_empty (deps))
 319     return true;
 320
 321   x = apply_schedule_on_deps (schedule, deps);
 322   space = isl_map_get_space (x);
 323   space = isl_space_range (space);
 324   lex = isl_map_lex_ge (space);
 325   x = isl_map_intersect (x, lex);
 326   res = isl_map_is_empty (x);
 327
 328   isl_map_free (x);
 329   return res;
 330 }
 331
 332 /* Return true when DEPS is non empty and the intersection of LEX with
 333    the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
 334    in which all the inputs before DEPTH occur at the same time as the
 335    output, and the input at DEPTH occurs before output.  */
 336
 337 bool
 338 carries_deps (__isl_keep isl_union_map *schedule,
 339               __isl_keep isl_union_map *deps,
 340               int depth)
 341 {
 342   bool res;
 343   int i;
 344   isl_space *space;
 345   isl_map *lex, *x;
 346   isl_constraint *ineq;
 347
 348   if (isl_union_map_is_empty (deps))
 349     return false;
 350
 351   x = apply_schedule_on_deps (schedule, deps);
 352   if (x == NULL)
 353     return false;
 354   space = isl_map_get_space (x);
 355   space = isl_space_range (space);
 356   lex = isl_map_lex_le (space);
 357   space = isl_map_get_space (x);
 358   ineq = isl_inequality_alloc (isl_local_space_from_space (space));
 359
 360   for (i = 0; i < depth - 1; i++)
 361     lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
 362
 363   /* in + 1 <= out  */
 364   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
 365   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
 366   ineq = isl_constraint_set_constant_si (ineq, -1);
 367   lex = isl_map_add_constraint (lex, ineq);
 368   x = isl_map_intersect (x, lex);
 369   res = !isl_map_is_empty (x);
 370
 371   isl_map_free (x);
 372   return res;
 373 }
 374
 375 /* Subtract from the RAW, WAR, and WAW dependences those relations
 376    that have been marked as belonging to an associative commutative
 377    reduction.  */
 378
 379 static void
 380 subtract_commutative_associative_deps (scop_p scop,
 381                                        vec<poly_bb_p> pbbs,
 382                                        isl_union_map *original,
 383                                        isl_union_map **must_raw,
 384                                        isl_union_map **may_raw,
 385                                        isl_union_map **must_raw_no_source,
 386                                        isl_union_map **may_raw_no_source,
 387                                        isl_union_map **must_war,
 388                                        isl_union_map **may_war,
 389                                        isl_union_map **must_war_no_source,
 390                                        isl_union_map **may_war_no_source,
 391                                        isl_union_map **must_waw,
 392                                        isl_union_map **may_waw,
 393                                        isl_union_map **must_waw_no_source,
 394                                        isl_union_map **may_waw_no_source)
 395 {
 396   int i, j;
 397   poly_bb_p pbb;
 398   poly_dr_p pdr;
 399   isl_space *space = isl_set_get_space (scop->context);
 400
 401   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 402     if (PBB_IS_REDUCTION (pbb))
 403       {
 404         int res;
 405         isl_union_map *r = isl_union_map_empty (isl_space_copy (space));
 406         isl_union_map *must_w = isl_union_map_empty (isl_space_copy (space));
 407         isl_union_map *may_w = isl_union_map_empty (isl_space_copy (space));
 408         isl_union_map *all_w;
 409         isl_union_map *empty;
 410         isl_union_map *x_must_raw;
 411         isl_union_map *x_may_raw;
 412         isl_union_map *x_must_raw_no_source;
 413         isl_union_map *x_may_raw_no_source;
 414         isl_union_map *x_must_war;
 415         isl_union_map *x_may_war;
 416         isl_union_map *x_must_war_no_source;
 417         isl_union_map *x_may_war_no_source;
 418         isl_union_map *x_must_waw;
 419         isl_union_map *x_may_waw;
 420         isl_union_map *x_must_waw_no_source;
 421         isl_union_map *x_may_waw_no_source;
 422
 423         FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 424           if (pdr_read_p (pdr))
 425             r = isl_union_map_add_map (r, add_pdr_constraints (pdr, pbb));
 426
 427         FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 428           if (pdr_write_p (pdr))
 429             must_w = isl_union_map_add_map (must_w,
 430                                             add_pdr_constraints (pdr, pbb));
 431
 432         FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 433           if (pdr_may_write_p (pdr))
 434             may_w = isl_union_map_add_map (may_w,
 435                                            add_pdr_constraints (pdr, pbb));
 436
 437         all_w = isl_union_map_union
 438           (isl_union_map_copy (must_w), isl_union_map_copy (may_w));
 439         empty = isl_union_map_empty (isl_union_map_get_space (all_w));
 440
 441         res = isl_union_map_compute_flow (isl_union_map_copy (r),
 442                                           isl_union_map_copy (must_w),
 443                                           isl_union_map_copy (may_w),
 444                                           isl_union_map_copy (original),
 445                                           &x_must_raw, &x_may_raw,
 446                                           &x_must_raw_no_source,
 447                                           &x_may_raw_no_source);
 448         gcc_assert (res == 0);
 449         res = isl_union_map_compute_flow (isl_union_map_copy (all_w),
 450                                           r, empty,
 451                                           isl_union_map_copy (original),
 452                                           &x_must_war, &x_may_war,
 453                                           &x_must_war_no_source,
 454                                           &x_may_war_no_source);
 455         gcc_assert (res == 0);
 456         res = isl_union_map_compute_flow (all_w, must_w, may_w,
 457                                           isl_union_map_copy (original),
 458                                           &x_must_waw, &x_may_waw,
 459                                           &x_must_waw_no_source,
 460                                           &x_may_waw_no_source);
 461         gcc_assert (res == 0);
 462
 463         if (must_raw)
 464           *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
 465         else
 466           isl_union_map_free (x_must_raw);
 467
 468         if (may_raw)
 469           *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
 470         else
 471           isl_union_map_free (x_may_raw);
 472
 473         if (must_raw_no_source)
 474           *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
 475                                                         x_must_raw_no_source);
 476         else
 477           isl_union_map_free (x_must_raw_no_source);
 478
 479         if (may_raw_no_source)
 480           *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
 481                                                        x_may_raw_no_source);
 482         else
 483           isl_union_map_free (x_may_raw_no_source);
 484
 485         if (must_war)
 486           *must_war = isl_union_map_subtract (*must_war, x_must_war);
 487         else
 488           isl_union_map_free (x_must_war);
 489
 490         if (may_war)
 491           *may_war = isl_union_map_subtract (*may_war, x_may_war);
 492         else
 493           isl_union_map_free (x_may_war);
 494
 495         if (must_war_no_source)
 496           *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
 497                                                         x_must_war_no_source);
 498         else
 499           isl_union_map_free (x_must_war_no_source);
 500
 501         if (may_war_no_source)
 502           *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
 503                                                        x_may_war_no_source);
 504         else
 505           isl_union_map_free (x_may_war_no_source);
 506
 507         if (must_waw)
 508           *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
 509         else
 510           isl_union_map_free (x_must_waw);
 511
 512         if (may_waw)
 513           *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
 514         else
 515           isl_union_map_free (x_may_waw);
 516
 517         if (must_waw_no_source)
 518           *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
 519                                                         x_must_waw_no_source);
 520         else
 521           isl_union_map_free (x_must_waw_no_source);
 522
 523         if (may_waw_no_source)
 524           *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
 525                                                        x_may_waw_no_source);
 526         else
 527           isl_union_map_free (x_may_waw_no_source);
 528       }
 529
 530   isl_union_map_free (original);
 531   isl_space_free (space);
 532 }
 533
 534 /* Compute the original data dependences in SCOP for all the reads and
 535    writes in PBBS.  */
 536
 537 void
 538 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
 539               isl_union_map **must_raw,
 540               isl_union_map **may_raw,
 541               isl_union_map **must_raw_no_source,
 542               isl_union_map **may_raw_no_source,
 543               isl_union_map **must_war,
 544               isl_union_map **may_war,
 545               isl_union_map **must_war_no_source,
 546               isl_union_map **may_war_no_source,
 547               isl_union_map **must_waw,
 548               isl_union_map **may_waw,
 549               isl_union_map **must_waw_no_source,
 550               isl_union_map **may_waw_no_source)
 551 {
 552   isl_union_map *reads = scop_get_reads (scop, pbbs);
 553   isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
 554   isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
 555   isl_union_map *all_writes = isl_union_map_union
 556     (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
 557   isl_space *space = isl_union_map_get_space (all_writes);
 558   isl_union_map *empty = isl_union_map_empty (space);
 559   isl_union_map *original = scop_get_original_schedule (scop, pbbs);
 560   int res;
 561
 562   res = isl_union_map_compute_flow (isl_union_map_copy (reads),
 563                                     isl_union_map_copy (must_writes),
 564                                     isl_union_map_copy (may_writes),
 565                                     isl_union_map_copy (original),
 566                                     must_raw, may_raw, must_raw_no_source,
 567                                     may_raw_no_source);
 568   gcc_assert (res == 0);
 569   res = isl_union_map_compute_flow (isl_union_map_copy (all_writes),
 570                                     reads, empty,
 571                                     isl_union_map_copy (original),
 572                                     must_war, may_war, must_war_no_source,
 573                                     may_war_no_source);
 574   gcc_assert (res == 0);
 575   res = isl_union_map_compute_flow (all_writes, must_writes, may_writes,
 576                                     isl_union_map_copy (original),
 577                                     must_waw, may_waw, must_waw_no_source,
 578                                     may_waw_no_source);
 579   gcc_assert (res == 0);
 580
 581   subtract_commutative_associative_deps
 582     (scop, pbbs, original,
 583      must_raw, may_raw, must_raw_no_source, may_raw_no_source,
 584      must_war, may_war, must_war_no_source, may_war_no_source,
 585      must_waw, may_waw, must_waw_no_source, may_waw_no_source);
 586 }
 587
 588 /* Given a TRANSFORM, check whether it respects the original
 589    dependences in SCOP.  Returns true when TRANSFORM is a safe
 590    transformation.  */
 591
 592 static bool
 593 transform_is_safe (scop_p scop, isl_union_map *transform)
 594 {
 595   bool res;
 596
 597   if (!scop->must_raw)
 598     compute_deps (scop, SCOP_BBS (scop),
 599                   &scop->must_raw, &scop->may_raw,
 600                   &scop->must_raw_no_source, &scop->may_raw_no_source,
 601                   &scop->must_war, &scop->may_war,
 602                   &scop->must_war_no_source, &scop->may_war_no_source,
 603                   &scop->must_waw, &scop->may_waw,
 604                   &scop->must_waw_no_source, &scop->may_waw_no_source);
 605
 606   res = (no_violations (transform, scop->must_raw)
 607          && no_violations (transform, scop->may_raw)
 608          && no_violations (transform, scop->must_war)
 609          && no_violations (transform, scop->may_war)
 610          && no_violations (transform, scop->must_waw)
 611          && no_violations (transform, scop->may_waw));
 612
 613   isl_union_map_free (transform);
 614   return res;
 615 }
 616
 617 /* Return true when the SCOP transformed schedule is correct.  */
 618
 619 bool
 620 graphite_legal_transform (scop_p scop)
 621 {
 622   int res;
 623   isl_union_map *transform;
 624
 625   timevar_push (TV_GRAPHITE_DATA_DEPS);
 626   transform = scop_get_transformed_schedule (scop, SCOP_BBS (scop));
 627   res = transform_is_safe (scop, transform);
 628   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 629
 630   return res;
 631 }
 632
 633 /* Return true when the loop at DEPTH carries dependences.  BODY is
 634    the body of the loop.  */
 635
 636 static bool
 637 loop_level_carries_dependences (scop_p scop, vec<poly_bb_p> body,
 638                                 int depth)
 639 {
 640   isl_union_map *transform = scop_get_transformed_schedule (scop, body);
 641   isl_union_map *must_raw, *may_raw;
 642   isl_union_map *must_war, *may_war;
 643   isl_union_map *must_waw, *may_waw;
 644   int res;
 645
 646   compute_deps (scop, body,
 647                 &must_raw, &may_raw, NULL, NULL,
 648                 &must_war, &may_war, NULL, NULL,
 649                 &must_waw, &may_waw, NULL, NULL);
 650
 651   res = (carries_deps (transform, must_raw, depth)
 652          || carries_deps (transform, may_raw, depth)
 653          || carries_deps (transform, must_war, depth)
 654          || carries_deps (transform, may_war, depth)
 655          || carries_deps (transform, must_waw, depth)
 656          || carries_deps (transform, may_waw, depth));
 657
 658   isl_union_map_free (transform);
 659   isl_union_map_free (must_raw);
 660   isl_union_map_free (may_raw);
 661   isl_union_map_free (must_war);
 662   isl_union_map_free (may_war);
 663   isl_union_map_free (must_waw);
 664   isl_union_map_free (may_waw);
 665   return res;
 666 }
 667
 668 /* Returns true when the loop L at level DEPTH is parallel.
 669    BB_PBB_MAPPING is a map between a basic_block and its related
 670    poly_bb_p.  */
 671
 672 bool
 673 loop_is_parallel_p (loop_p loop, bb_pbb_htab_type *bb_pbb_mapping, int depth)
 674 {
 675   bool dependences;
 676   scop_p scop;
 677
 678   timevar_push (TV_GRAPHITE_DATA_DEPS);
 679   auto_vec<poly_bb_p, 3> body;
 680   scop = get_loop_body_pbbs (loop, bb_pbb_mapping, &body);
 681   dependences = loop_level_carries_dependences (scop, body, depth);
 682   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 683
 684   return !dependences;
 685 }
 686
 687 #endif