gcc/graphite-dependences.c

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