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