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   isl_stat res;
 260   struct extend_schedule_str str;
 261
 262   res = isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
 263   gcc_assert (res == isl_stat_ok);
 264
 265   str.max = max;
 266   str.umap = isl_union_map_empty (isl_union_map_get_space (x));
 267   res = isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
 268   gcc_assert (res == isl_stat_ok);
 269
 270   isl_union_map_free (x);
 271   return str.umap;
 272 }
 273
 274 /* Applies SCHEDULE to the in and out dimensions of the dependences
 275    DEPS and return the resulting relation.  */
 276
 277 static isl_map *
 278 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
 279                         __isl_keep isl_union_map *deps)
 280 {
 281   isl_map *x;
 282   isl_union_map *ux, *trans;
 283
 284   trans = isl_union_map_copy (schedule);
 285   trans = extend_schedule (trans);
 286   ux = isl_union_map_copy (deps);
 287   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
 288   ux = isl_union_map_apply_range (ux, trans);
 289   if (isl_union_map_is_empty (ux))
 290     {
 291       isl_union_map_free (ux);
 292       return NULL;
 293     }
 294   x = isl_map_from_union_map (ux);
 295
 296   return x;
 297 }
 298
 299 /* Return true when SCHEDULE does not violate the data DEPS: that is
 300    when the intersection of LEX with the DEPS transformed by SCHEDULE
 301    is empty.  LEX is the relation in which the outputs occur before
 302    the inputs.  */
 303
 304 static bool
 305 no_violations (__isl_keep isl_union_map *schedule,
 306                __isl_keep isl_union_map *deps)
 307 {
 308   bool res;
 309   isl_space *space;
 310   isl_map *lex, *x;
 311
 312   if (isl_union_map_is_empty (deps))
 313     return true;
 314
 315   x = apply_schedule_on_deps (schedule, deps);
 316   space = isl_map_get_space (x);
 317   space = isl_space_range (space);
 318   lex = isl_map_lex_ge (space);
 319   x = isl_map_intersect (x, lex);
 320   res = isl_map_is_empty (x);
 321
 322   isl_map_free (x);
 323   return res;
 324 }
 325
 326 /* Return true when DEPS is non empty and the intersection of LEX with
 327    the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
 328    in which all the inputs before DEPTH occur at the same time as the
 329    output, and the input at DEPTH occurs before output.  */
 330
 331 bool
 332 carries_deps (__isl_keep isl_union_map *schedule,
 333               __isl_keep isl_union_map *deps,
 334               int depth)
 335 {
 336   bool res;
 337   int i;
 338   isl_space *space;
 339   isl_map *lex, *x;
 340   isl_constraint *ineq;
 341
 342   if (isl_union_map_is_empty (deps))
 343     return false;
 344
 345   x = apply_schedule_on_deps (schedule, deps);
 346   if (x == NULL)
 347     return false;
 348   space = isl_map_get_space (x);
 349   space = isl_space_range (space);
 350   lex = isl_map_lex_le (space);
 351   space = isl_map_get_space (x);
 352   ineq = isl_inequality_alloc (isl_local_space_from_space (space));
 353
 354   for (i = 0; i < depth - 1; i++)
 355     lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
 356
 357   /* in + 1 <= out  */
 358   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
 359   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
 360   ineq = isl_constraint_set_constant_si (ineq, -1);
 361   lex = isl_map_add_constraint (lex, ineq);
 362   x = isl_map_intersect (x, lex);
 363   res = !isl_map_is_empty (x);
 364
 365   isl_map_free (x);
 366   return res;
 367 }
 368
 369 /* Subtract from the RAW, WAR, and WAW dependences those relations
 370    that have been marked as belonging to an associative commutative
 371    reduction.  */
 372
 373 static void
 374 subtract_commutative_associative_deps (scop_p scop,
 375                                        vec<poly_bb_p> pbbs,
 376                                        isl_union_map *original,
 377                                        isl_union_map **must_raw,
 378                                        isl_union_map **may_raw,
 379                                        isl_union_map **must_raw_no_source,
 380                                        isl_union_map **may_raw_no_source,
 381                                        isl_union_map **must_war,
 382                                        isl_union_map **may_war,
 383                                        isl_union_map **must_war_no_source,
 384                                        isl_union_map **may_war_no_source,
 385                                        isl_union_map **must_waw,
 386                                        isl_union_map **may_waw,
 387                                        isl_union_map **must_waw_no_source,
 388                                        isl_union_map **may_waw_no_source)
 389 {
 390   int i, j;
 391   poly_bb_p pbb;
 392   poly_dr_p pdr;
 393   isl_space *space = isl_set_get_space (scop->context);
 394
 395   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 396     if (PBB_IS_REDUCTION (pbb))
 397       {
 398         int res;
 399         isl_union_map *r = isl_union_map_empty (isl_space_copy (space));
 400         isl_union_map *must_w = isl_union_map_empty (isl_space_copy (space));
 401         isl_union_map *may_w = isl_union_map_empty (isl_space_copy (space));
 402         isl_union_map *all_w;
 403         isl_union_map *empty;
 404         isl_union_map *x_must_raw;
 405         isl_union_map *x_may_raw;
 406         isl_union_map *x_must_raw_no_source;
 407         isl_union_map *x_may_raw_no_source;
 408         isl_union_map *x_must_war;
 409         isl_union_map *x_may_war;
 410         isl_union_map *x_must_war_no_source;
 411         isl_union_map *x_may_war_no_source;
 412         isl_union_map *x_must_waw;
 413         isl_union_map *x_may_waw;
 414         isl_union_map *x_must_waw_no_source;
 415         isl_union_map *x_may_waw_no_source;
 416
 417         FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 418           if (pdr_read_p (pdr))
 419             r = isl_union_map_add_map (r, add_pdr_constraints (pdr, pbb));
 420
 421         FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 422           if (pdr_write_p (pdr))
 423             must_w = isl_union_map_add_map (must_w,
 424                                             add_pdr_constraints (pdr, pbb));
 425
 426         FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 427           if (pdr_may_write_p (pdr))
 428             may_w = isl_union_map_add_map (may_w,
 429                                            add_pdr_constraints (pdr, pbb));
 430
 431         all_w = isl_union_map_union
 432           (isl_union_map_copy (must_w), isl_union_map_copy (may_w));
 433         empty = isl_union_map_empty (isl_union_map_get_space (all_w));
 434
 435         res = isl_union_map_compute_flow (isl_union_map_copy (r),
 436                                           isl_union_map_copy (must_w),
 437                                           isl_union_map_copy (may_w),
 438                                           isl_union_map_copy (original),
 439                                           &x_must_raw, &x_may_raw,
 440                                           &x_must_raw_no_source,
 441                                           &x_may_raw_no_source);
 442         gcc_assert (res == 0);
 443         res = isl_union_map_compute_flow (isl_union_map_copy (all_w),
 444                                           r, empty,
 445                                           isl_union_map_copy (original),
 446                                           &x_must_war, &x_may_war,
 447                                           &x_must_war_no_source,
 448                                           &x_may_war_no_source);
 449         gcc_assert (res == 0);
 450         res = isl_union_map_compute_flow (all_w, must_w, may_w,
 451                                           isl_union_map_copy (original),
 452                                           &x_must_waw, &x_may_waw,
 453                                           &x_must_waw_no_source,
 454                                           &x_may_waw_no_source);
 455         gcc_assert (res == 0);
 456
 457         if (must_raw)
 458           *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
 459         else
 460           isl_union_map_free (x_must_raw);
 461
 462         if (may_raw)
 463           *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
 464         else
 465           isl_union_map_free (x_may_raw);
 466
 467         if (must_raw_no_source)
 468           *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
 469                                                         x_must_raw_no_source);
 470         else
 471           isl_union_map_free (x_must_raw_no_source);
 472
 473         if (may_raw_no_source)
 474           *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
 475                                                        x_may_raw_no_source);
 476         else
 477           isl_union_map_free (x_may_raw_no_source);
 478
 479         if (must_war)
 480           *must_war = isl_union_map_subtract (*must_war, x_must_war);
 481         else
 482           isl_union_map_free (x_must_war);
 483
 484         if (may_war)
 485           *may_war = isl_union_map_subtract (*may_war, x_may_war);
 486         else
 487           isl_union_map_free (x_may_war);
 488
 489         if (must_war_no_source)
 490           *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
 491                                                         x_must_war_no_source);
 492         else
 493           isl_union_map_free (x_must_war_no_source);
 494
 495         if (may_war_no_source)
 496           *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
 497                                                        x_may_war_no_source);
 498         else
 499           isl_union_map_free (x_may_war_no_source);
 500
 501         if (must_waw)
 502           *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
 503         else
 504           isl_union_map_free (x_must_waw);
 505
 506         if (may_waw)
 507           *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
 508         else
 509           isl_union_map_free (x_may_waw);
 510
 511         if (must_waw_no_source)
 512           *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
 513                                                         x_must_waw_no_source);
 514         else
 515           isl_union_map_free (x_must_waw_no_source);
 516
 517         if (may_waw_no_source)
 518           *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
 519                                                        x_may_waw_no_source);
 520         else
 521           isl_union_map_free (x_may_waw_no_source);
 522       }
 523
 524   isl_union_map_free (original);
 525   isl_space_free (space);
 526 }
 527
 528 /* Compute the original data dependences in SCOP for all the reads and
 529    writes in PBBS.  */
 530
 531 void
 532 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
 533               isl_union_map **must_raw,
 534               isl_union_map **may_raw,
 535               isl_union_map **must_raw_no_source,
 536               isl_union_map **may_raw_no_source,
 537               isl_union_map **must_war,
 538               isl_union_map **may_war,
 539               isl_union_map **must_war_no_source,
 540               isl_union_map **may_war_no_source,
 541               isl_union_map **must_waw,
 542               isl_union_map **may_waw,
 543               isl_union_map **must_waw_no_source,
 544               isl_union_map **may_waw_no_source)
 545 {
 546   isl_union_map *reads = scop_get_reads (scop, pbbs);
 547   isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
 548   isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
 549   isl_union_map *all_writes = isl_union_map_union
 550     (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
 551   isl_space *space = isl_union_map_get_space (all_writes);
 552   isl_union_map *empty = isl_union_map_empty (space);
 553   isl_union_map *original = scop_get_original_schedule (scop, pbbs);
 554   int res;
 555
 556   res = isl_union_map_compute_flow (isl_union_map_copy (reads),
 557                                     isl_union_map_copy (must_writes),
 558                                     isl_union_map_copy (may_writes),
 559                                     isl_union_map_copy (original),
 560                                     must_raw, may_raw, must_raw_no_source,
 561                                     may_raw_no_source);
 562   gcc_assert (res == 0);
 563   res = isl_union_map_compute_flow (isl_union_map_copy (all_writes),
 564                                     reads, empty,
 565                                     isl_union_map_copy (original),
 566                                     must_war, may_war, must_war_no_source,
 567                                     may_war_no_source);
 568   gcc_assert (res == 0);
 569   res = isl_union_map_compute_flow (all_writes, must_writes, may_writes,
 570                                     isl_union_map_copy (original),
 571                                     must_waw, may_waw, must_waw_no_source,
 572                                     may_waw_no_source);
 573   gcc_assert (res == 0);
 574
 575   subtract_commutative_associative_deps
 576     (scop, pbbs, original,
 577      must_raw, may_raw, must_raw_no_source, may_raw_no_source,
 578      must_war, may_war, must_war_no_source, may_war_no_source,
 579      must_waw, may_waw, must_waw_no_source, may_waw_no_source);
 580 }
 581
 582 /* Given a TRANSFORM, check whether it respects the original
 583    dependences in SCOP.  Returns true when TRANSFORM is a safe
 584    transformation.  */
 585
 586 static bool
 587 transform_is_safe (scop_p scop, isl_union_map *transform)
 588 {
 589   bool res;
 590
 591   if (!scop->must_raw)
 592     compute_deps (scop, SCOP_BBS (scop),
 593                   &scop->must_raw, &scop->may_raw,
 594                   &scop->must_raw_no_source, &scop->may_raw_no_source,
 595                   &scop->must_war, &scop->may_war,
 596                   &scop->must_war_no_source, &scop->may_war_no_source,
 597                   &scop->must_waw, &scop->may_waw,
 598                   &scop->must_waw_no_source, &scop->may_waw_no_source);
 599
 600   res = (no_violations (transform, scop->must_raw)
 601          && no_violations (transform, scop->may_raw)
 602          && no_violations (transform, scop->must_war)
 603          && no_violations (transform, scop->may_war)
 604          && no_violations (transform, scop->must_waw)
 605          && no_violations (transform, scop->may_waw));
 606
 607   isl_union_map_free (transform);
 608   return res;
 609 }
 610
 611 /* Return true when the SCOP transformed schedule is correct.  */
 612
 613 bool
 614 graphite_legal_transform (scop_p scop)
 615 {
 616   int res;
 617   isl_union_map *transform;
 618
 619   timevar_push (TV_GRAPHITE_DATA_DEPS);
 620   transform = scop_get_transformed_schedule (scop, SCOP_BBS (scop));
 621   res = transform_is_safe (scop, transform);
 622   timevar_pop (TV_GRAPHITE_DATA_DEPS);
 623
 624   return res;
 625 }
 626
 627 #endif /* HAVE_isl */