gcc/graphite-dependences.c

   1 /* Data dependence analysis for Graphite.
   2    Copyright (C) 2009-2013 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         *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
 428         *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
 429         *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
 430                                                       x_must_raw_no_source);
 431         *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
 432                                                      x_may_raw_no_source);
 433         *must_war = isl_union_map_subtract (*must_war, x_must_war);
 434         *may_war = isl_union_map_subtract (*may_war, x_may_war);
 435         *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
 436                                                       x_must_war_no_source);
 437         *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
 438                                                      x_may_war_no_source);
 439         *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
 440         *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
 441         *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
 442                                                       x_must_waw_no_source);
 443         *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
 444                                                      x_may_waw_no_source);
 445       }
 446
 447   isl_union_map_free (original);
 448   isl_space_free (space);
 449 }
 450
 451 /* Compute the original data dependences in SCOP for all the reads and
 452    writes in PBBS.  */
 453
 454 void
 455 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
 456               isl_union_map **must_raw,
 457               isl_union_map **may_raw,
 458               isl_union_map **must_raw_no_source,
 459               isl_union_map **may_raw_no_source,
 460               isl_union_map **must_war,
 461               isl_union_map **may_war,
 462               isl_union_map **must_war_no_source,
 463               isl_union_map **may_war_no_source,
 464               isl_union_map **must_waw,
 465               isl_union_map **may_waw,
 466               isl_union_map **must_waw_no_source,
 467               isl_union_map **may_waw_no_source)
 468 {
 469   isl_union_map *reads = scop_get_reads (scop, pbbs);
 470   isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
 471   isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
 472   isl_union_map *all_writes = isl_union_map_union
 473     (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
 474   isl_space *space = isl_union_map_get_space (all_writes);
 475   isl_union_map *empty = isl_union_map_empty (space);
 476   isl_union_map *original = scop_get_original_schedule (scop, pbbs);
 477   int res;
 478
 479   res = isl_union_map_compute_flow (isl_union_map_copy (reads),
 480                                     isl_union_map_copy (must_writes),
 481                                     isl_union_map_copy (may_writes),
 482                                     isl_union_map_copy (original),
 483                                     must_raw, may_raw, must_raw_no_source,
 484                                     may_raw_no_source);
 485   gcc_assert (res == 0);
 486   res = isl_union_map_compute_flow (isl_union_map_copy (all_writes),
 487                                     reads, empty,
 488                                     isl_union_map_copy (original),
 489                                     must_war, may_war, must_war_no_source,
 490                                     may_war_no_source);
 491   gcc_assert (res == 0);
 492   res = isl_union_map_compute_flow (all_writes, must_writes, may_writes,
 493                                     isl_union_map_copy (original),
 494                                     must_waw, may_waw, must_waw_no_source,
 495                                     may_waw_no_source);
 496   gcc_assert (res == 0);
 497
 498   subtract_commutative_associative_deps
 499     (scop, pbbs, original,
 500      must_raw, may_raw, must_raw_no_source, may_raw_no_source,
 501      must_war, may_war, must_war_no_source, may_war_no_source,
 502      must_waw, may_waw, must_waw_no_source, may_waw_no_source);
 503 }
 504
 505 /* Given a TRANSFORM, check whether it respects the original
 506    dependences in SCOP.  Returns true when TRANSFORM is a safe
 507    transformation.  */
 508
 509 static bool
 510 transform_is_safe (scop_p scop, isl_union_map *transform)
 511 {
 512   bool res;
 513
 514   if (!scop->must_raw)
 515     compute_deps (scop, SCOP_BBS (scop),
 516                   &scop->must_raw, &scop->may_raw,
 517                   &scop->must_raw_no_source, &scop->may_raw_no_source,
 518                   &scop->must_war, &scop->may_war,
 519                   &scop->must_war_no_source, &scop->may_war_no_source,
 520                   &scop->must_waw, &scop->may_waw,
 521                   &scop->must_waw_no_source, &scop->may_waw_no_source);
 522
 523   res = (no_violations (transform, scop->must_raw)
 524          && no_violations (transform, scop->may_raw)
 525          && no_violations (transform, scop->must_war)
 526          && no_violations (transform, scop->may_war)
 527          && no_violations (transform, scop->must_waw)
 528          && no_violations (transform, scop->may_waw));
 529
 530   isl_union_map_free (transform);
 531   return res;
 532 }
 533
 534 /* Return true when the SCOP transformed schedule is correct.  */
 535
 536 bool
 537 graphite_legal_transform (scop_p scop)
 538 {
 539   int res;
 540   isl_union_map *transform;
 541
 542   timevar_push (TV_GRAPHITE_DATA_DEPS);
 543   transform = scop_get_transformed_schedule (scop, SCOP_BBS (scop));
 544   res = transform_is_safe (scop, transform);
 545   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 546
 547   return res;
 548 }
 549
 550 /* Return true when the loop at DEPTH carries dependences.  BODY is
 551    the body of the loop.  */
 552
 553 static bool
 554 loop_level_carries_dependences (scop_p scop, vec<poly_bb_p> body,
 555                                 int depth)
 556 {
 557   isl_union_map *transform = scop_get_transformed_schedule (scop, body);
 558   isl_union_map *must_raw, *may_raw;
 559   isl_union_map *must_war, *may_war;
 560   isl_union_map *must_waw, *may_waw;
 561   int res;
 562
 563   compute_deps (scop, body,
 564                 &must_raw, &may_raw, NULL, NULL,
 565                 &must_war, &may_war, NULL, NULL,
 566                 &must_waw, &may_waw, NULL, NULL);
 567
 568   res = (carries_deps (transform, must_raw, depth)
 569          || carries_deps (transform, may_raw, depth)
 570          || carries_deps (transform, must_war, depth)
 571          || carries_deps (transform, may_war, depth)
 572          || carries_deps (transform, must_waw, depth)
 573          || carries_deps (transform, may_waw, depth));
 574
 575   isl_union_map_free (transform);
 576   isl_union_map_free (must_raw);
 577   isl_union_map_free (may_raw);
 578   isl_union_map_free (must_war);
 579   isl_union_map_free (may_war);
 580   isl_union_map_free (must_waw);
 581   isl_union_map_free (may_waw);
 582   return res;
 583 }
 584
 585 /* Returns true when the loop L at level DEPTH is parallel.
 586    BB_PBB_MAPPING is a map between a basic_block and its related
 587    poly_bb_p.  */
 588
 589 bool
 590 loop_is_parallel_p (loop_p loop, bb_pbb_htab_type bb_pbb_mapping, int depth)
 591 {
 592   bool dependences;
 593   scop_p scop;
 594
 595   timevar_push (TV_GRAPHITE_DATA_DEPS);
 596   stack_vec<poly_bb_p, 3> body;
 597   scop = get_loop_body_pbbs (loop, bb_pbb_mapping, &body);
 598   dependences = loop_level_carries_dependences (scop, body, depth);
 599   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 600
 601   return !dependences;
 602 }
 603
 604 #endif