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