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