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