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