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