gcc/graphite-dependences.c

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