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 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   for (i = 0; i < depth - 1; 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, depth - 1, 1);
 321   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -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> 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 (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 (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 (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 (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> 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> 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, bb_pbb_htab_type bb_pbb_mapping, int depth)
 583 {
 584   bool dependences;
 585   scop_p scop;
 586   vec<poly_bb_p> body;
 587   body.create (3);
 588
 589   timevar_push (TV_GRAPHITE_DATA_DEPS);
 590   scop = get_loop_body_pbbs (loop, bb_pbb_mapping, &body);
 591   dependences = loop_level_carries_dependences (scop, body, depth);
 592   body.release ();
 593   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 594
 595   return !dependences;
 596 }
 597
 598 #endif