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