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