gcc/graphite-dependences.c

   1 /* Data dependence analysis for Graphite.
   2    Copyright (C) 2009-2017 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 #define USES_ISL
  23
  24 #include "config.h"
  25
  26 #ifdef HAVE_isl
  27
  28 #include "system.h"
  29 #include "coretypes.h"
  30 #include "backend.h"
  31 #include "cfghooks.h"
  32 #include "tree.h"
  33 #include "gimple.h"
  34 #include "fold-const.h"
  35 #include "gimple-iterator.h"
  36 #include "tree-ssa-loop.h"
  37 #include "tree-pass.h"
  38 #include "cfgloop.h"
  39 #include "tree-data-ref.h"
  40 #include "graphite.h"
  41
  42 /* Add the constraints from the set S to the domain of MAP.  */
  43
  44 static isl_map *
  45 constrain_domain (isl_map *map, isl_set *s)
  46 {
  47   isl_space *d = isl_map_get_space (map);
  48   isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
  49
  50   s = isl_set_set_tuple_id (s, id);
  51   isl_space_free (d);
  52   return isl_map_coalesce (isl_map_intersect_domain (map, s));
  53 }
  54
  55 /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain.  */
  56
  57 static isl_map *
  58 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
  59 {
  60   isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
  61                                         isl_set_copy (pdr->subscript_sizes));
  62   x = isl_map_coalesce (x);
  63   return constrain_domain (x, isl_set_copy (pbb->domain));
  64 }
  65
  66 /* Returns all the memory reads in SCOP.  */
  67
  68 static isl_union_map *
  69 scop_get_reads (scop_p scop)
  70 {
  71   int i, j;
  72   poly_bb_p pbb;
  73   poly_dr_p pdr;
  74   isl_space *space = isl_set_get_space (scop->param_context);
  75   isl_union_map *res = isl_union_map_empty (space);
  76
  77   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
  78     {
  79       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
  80         if (pdr_read_p (pdr))
  81           {
  82             if (dump_file)
  83               {
  84                 fprintf (dump_file, "Adding read to depedence graph: ");
  85                 print_pdr (dump_file, pdr);
  86               }
  87             isl_union_map *um
  88               = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
  89             res = isl_union_map_union (res, um);
  90             if (dump_file)
  91               {
  92                 fprintf (dump_file, "Reads depedence graph: ");
  93                 print_isl_union_map (dump_file, res);
  94               }
  95           }
  96     }
  97
  98   return isl_union_map_coalesce (res);
  99 }
 100
 101 /* Returns all the memory must writes in SCOP.  */
 102
 103 static isl_union_map *
 104 scop_get_must_writes (scop_p scop)
 105 {
 106   int i, j;
 107   poly_bb_p pbb;
 108   poly_dr_p pdr;
 109   isl_space *space = isl_set_get_space (scop->param_context);
 110   isl_union_map *res = isl_union_map_empty (space);
 111
 112   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 113     {
 114       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 115         if (pdr_write_p (pdr))
 116           {
 117             if (dump_file)
 118               {
 119                 fprintf (dump_file, "Adding must write to depedence graph: ");
 120                 print_pdr (dump_file, pdr);
 121               }
 122             isl_union_map *um
 123               = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
 124             res = isl_union_map_union (res, um);
 125             if (dump_file)
 126               {
 127                 fprintf (dump_file, "Must writes depedence graph: ");
 128                 print_isl_union_map (dump_file, res);
 129               }
 130           }
 131     }
 132
 133   return isl_union_map_coalesce (res);
 134 }
 135
 136 /* Returns all the memory may writes in SCOP.  */
 137
 138 static isl_union_map *
 139 scop_get_may_writes (scop_p scop)
 140 {
 141   int i, j;
 142   poly_bb_p pbb;
 143   poly_dr_p pdr;
 144   isl_space *space = isl_set_get_space (scop->param_context);
 145   isl_union_map *res = isl_union_map_empty (space);
 146
 147   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 148     {
 149       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 150         if (pdr_may_write_p (pdr))
 151           {
 152             if (dump_file)
 153               {
 154                 fprintf (dump_file, "Adding may write to depedence graph: ");
 155                 print_pdr (dump_file, pdr);
 156               }
 157             isl_union_map *um
 158               = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
 159             res = isl_union_map_union (res, um);
 160             if (dump_file)
 161               {
 162                 fprintf (dump_file, "May writes depedence graph: ");
 163                 print_isl_union_map (dump_file, res);
 164               }
 165           }
 166     }
 167
 168   return isl_union_map_coalesce (res);
 169 }
 170
 171 #ifndef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 172 /* Returns all the original schedules in SCOP.  */
 173
 174 static isl_union_map *
 175 scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
 176 {
 177   int i;
 178   poly_bb_p pbb;
 179   isl_space *space = isl_set_get_space (scop->param_context);
 180   isl_union_map *res = isl_union_map_empty (space);
 181
 182   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 183     {
 184       res = isl_union_map_add_map
 185         (res, constrain_domain (isl_map_copy (pbb->schedule),
 186                                 isl_set_copy (pbb->domain)));
 187     }
 188
 189   return isl_union_map_coalesce (res);
 190 }
 191 #endif
 192
 193 /* Helper function used on each MAP of a isl_union_map.  Computes the
 194    maximal output dimension.  */
 195
 196 static isl_stat
 197 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
 198 {
 199   int global_max = *((int *) user);
 200   isl_space *space = isl_map_get_space (map);
 201   int nb_out = isl_space_dim (space, isl_dim_out);
 202
 203   if (global_max < nb_out)
 204     *((int *) user) = nb_out;
 205
 206   isl_map_free (map);
 207   isl_space_free (space);
 208   return isl_stat_ok;
 209 }
 210
 211 /* Extends the output dimension of MAP to MAX dimensions.  */
 212
 213 static __isl_give isl_map *
 214 extend_map (__isl_take isl_map *map, int max)
 215 {
 216   isl_space *space = isl_map_get_space (map);
 217   int n = isl_space_dim (space, isl_dim_out);
 218
 219   isl_space_free (space);
 220   return isl_map_add_dims (map, isl_dim_out, max - n);
 221 }
 222
 223 /* Structure used to pass parameters to extend_schedule_1.  */
 224
 225 struct extend_schedule_str {
 226   int max;
 227   isl_union_map *umap;
 228 };
 229
 230 /* Helper function for extend_schedule.  */
 231
 232 static isl_stat
 233 extend_schedule_1 (__isl_take isl_map *map, void *user)
 234 {
 235   struct extend_schedule_str *str = (struct extend_schedule_str *) user;
 236   str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
 237   return isl_stat_ok;
 238 }
 239
 240 /* Return a relation that has uniform output dimensions.  */
 241
 242 static __isl_give isl_union_map *
 243 extend_schedule (__isl_take isl_union_map *x)
 244 {
 245   int max = 0;
 246   struct extend_schedule_str str;
 247
 248   isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
 249   str.max = max;
 250   str.umap = isl_union_map_empty (isl_union_map_get_space (x));
 251   isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
 252   isl_union_map_free (x);
 253   return isl_union_map_coalesce (str.umap);
 254 }
 255
 256 /* Applies SCHEDULE to the in and out dimensions of the dependences
 257    DEPS and return the resulting relation.  */
 258
 259 static isl_map *
 260 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
 261                         __isl_keep isl_union_map *deps)
 262 {
 263   isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
 264   isl_union_map *ux = isl_union_map_copy (deps);
 265   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
 266   ux = isl_union_map_apply_range (ux, trans);
 267   ux = isl_union_map_coalesce (ux);
 268
 269   if (!isl_union_map_is_empty (ux))
 270     return isl_map_from_union_map (ux);
 271
 272   isl_union_map_free (ux);
 273   return NULL;
 274 }
 275
 276 /* Return true when DEPS is non empty and the intersection of LEX with
 277    the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
 278    in which all the inputs before DEPTH occur at the same time as the
 279    output, and the input at DEPTH occurs before output.  */
 280
 281 bool
 282 carries_deps (__isl_keep isl_union_map *schedule,
 283               __isl_keep isl_union_map *deps,
 284               int depth)
 285 {
 286   if (isl_union_map_is_empty (deps))
 287     return false;
 288
 289   isl_map *x = apply_schedule_on_deps (schedule, deps);
 290   if (x == NULL)
 291     return false;
 292
 293   isl_space *space = isl_map_get_space (x);
 294   isl_map *lex = isl_map_lex_le (isl_space_range (space));
 295   isl_constraint *ineq = isl_inequality_alloc
 296     (isl_local_space_from_space (isl_map_get_space (x)));
 297
 298   for (int i = 0; i < depth - 1; i++)
 299     lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
 300
 301   /* in + 1 <= out  */
 302   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
 303   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
 304   ineq = isl_constraint_set_constant_si (ineq, -1);
 305   lex = isl_map_add_constraint (lex, ineq);
 306   lex = isl_map_coalesce (lex);
 307   x = isl_map_intersect (x, lex);
 308   bool res = !isl_map_is_empty (x);
 309
 310   isl_map_free (x);
 311   return res;
 312 }
 313
 314 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 315 /* Compute the dependence relations for the SCOP:
 316    RAW are read after write dependences,
 317    WAR are write after read dependences,
 318    WAW are write after write dependences.  */
 319
 320 void
 321 scop_get_dependences (scop_p scop)
 322 {
 323   if (scop->dependence)
 324     return;
 325
 326   isl_union_map *reads = scop_get_reads (scop);
 327   isl_union_map *must_writes = scop_get_must_writes (scop);
 328   isl_union_map *may_writes = scop_get_may_writes (scop);
 329
 330   if (dump_file)
 331     {
 332       fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
 333       fprintf (dump_file, "Statements on the iteration domain are mapped to"
 334                " array references.\n");
 335       fprintf (dump_file, "  To read the following data references:\n\n");
 336       fprintf (dump_file, "  S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
 337       fprintf (dump_file, "  S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
 338
 339       fprintf (dump_file, "  S_5[i0] is the dynamic instance of statement"
 340                " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
 341       fprintf (dump_file, "  [1, i0] is a 'memref' with alias set 1"
 342                " and first subscript access i0.\n");
 343       fprintf (dump_file, "  [106] is a 'scalar reference' which is the sum of"
 344                " SSA_NAME_VERSION 6"
 345                " and --param graphite-max-arrays-per-scop=100\n");
 346       fprintf (dump_file, "-----------------------\n\n");
 347
 348       fprintf (dump_file, "data references (\n");
 349       fprintf (dump_file, "  reads: ");
 350       print_isl_union_map (dump_file, reads);
 351       fprintf (dump_file, "  must_writes: ");
 352       print_isl_union_map (dump_file, must_writes);
 353       fprintf (dump_file, "  may_writes: ");
 354       print_isl_union_map (dump_file, may_writes);
 355       fprintf (dump_file, ")\n");
 356     }
 357
 358   gcc_assert (scop->original_schedule);
 359
 360   isl_union_access_info *ai;
 361   ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
 362   ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
 363   ai = isl_union_access_info_set_may_source (ai, may_writes);
 364   ai = isl_union_access_info_set_schedule
 365     (ai, isl_schedule_copy (scop->original_schedule));
 366   isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
 367   isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
 368   isl_union_flow_free (flow);
 369
 370   ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
 371   ai = isl_union_access_info_set_must_source (ai, must_writes);
 372   ai = isl_union_access_info_set_may_source (ai, reads);
 373   ai = isl_union_access_info_set_schedule
 374     (ai, isl_schedule_copy (scop->original_schedule));
 375   flow = isl_union_access_info_compute_flow (ai);
 376
 377   isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
 378   isl_union_map *war = isl_union_flow_get_may_dependence (flow);
 379   war = isl_union_map_subtract (war, isl_union_map_copy (waw));
 380   isl_union_flow_free (flow);
 381
 382   raw = isl_union_map_coalesce (raw);
 383   waw = isl_union_map_coalesce (waw);
 384   war = isl_union_map_coalesce (war);
 385
 386   isl_union_map *dependences = raw;
 387   dependences = isl_union_map_union (dependences, war);
 388   dependences = isl_union_map_union (dependences, waw);
 389   dependences = isl_union_map_coalesce (dependences);
 390
 391   if (dump_file)
 392     {
 393       fprintf (dump_file, "data dependences (\n");
 394       print_isl_union_map (dump_file, dependences);
 395       fprintf (dump_file, ")\n");
 396     }
 397
 398   scop->dependence = dependences;
 399 }
 400
 401 #else
 402
 403 /* Compute the original data dependences in SCOP for all the reads and
 404    writes in PBBS.  */
 405
 406 static void
 407 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
 408               isl_union_map **must_raw,
 409               isl_union_map **may_raw,
 410               isl_union_map **must_raw_no_source,
 411               isl_union_map **may_raw_no_source,
 412               isl_union_map **must_war,
 413               isl_union_map **may_war,
 414               isl_union_map **must_war_no_source,
 415               isl_union_map **may_war_no_source,
 416               isl_union_map **must_waw,
 417               isl_union_map **may_waw,
 418               isl_union_map **must_waw_no_source,
 419               isl_union_map **may_waw_no_source)
 420 {
 421   isl_union_map *reads = scop_get_reads (scop);
 422   isl_union_map *must_writes = scop_get_must_writes (scop);
 423   isl_union_map *may_writes = scop_get_may_writes (scop);
 424   isl_union_map *all_writes = isl_union_map_union
 425     (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
 426   all_writes = isl_union_map_coalesce (all_writes);
 427
 428   isl_space *space = isl_union_map_get_space (all_writes);
 429   isl_union_map *empty = isl_union_map_empty (space);
 430   isl_union_map *original = scop_get_original_schedule (scop, pbbs);
 431
 432   if (dump_file)
 433     {
 434       fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
 435       fprintf (dump_file, "Statements on the iteration domain are mapped to"
 436                " array references.\n");
 437       fprintf (dump_file, "  To read the following data references:\n\n");
 438       fprintf (dump_file, "  S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
 439       fprintf (dump_file, "  S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
 440
 441       fprintf (dump_file, "  S_5[i0] is the dynamic instance of statement"
 442                " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
 443       fprintf (dump_file, "  [1, i0] is a 'memref' with alias set 1"
 444                " and first subscript access i0.\n");
 445       fprintf (dump_file, "  [106] is a 'scalar reference' which is the sum of"
 446                " SSA_NAME_VERSION 6"
 447                " and --param graphite-max-arrays-per-scop=100\n");
 448       fprintf (dump_file, "-----------------------\n\n");
 449
 450       fprintf (dump_file, "data references (\n");
 451       fprintf (dump_file, "  reads: ");
 452       print_isl_union_map (dump_file, reads);
 453       fprintf (dump_file, "  must_writes: ");
 454       print_isl_union_map (dump_file, must_writes);
 455       fprintf (dump_file, "  may_writes: ");
 456       print_isl_union_map (dump_file, may_writes);
 457       fprintf (dump_file, "  all_writes: ");
 458       print_isl_union_map (dump_file, all_writes);
 459       fprintf (dump_file, ")\n");
 460     }
 461
 462   isl_union_map_compute_flow (isl_union_map_copy (reads),
 463                               isl_union_map_copy (must_writes),
 464                               isl_union_map_copy (may_writes),
 465                               isl_union_map_copy (original),
 466                               must_raw, may_raw, must_raw_no_source,
 467                               may_raw_no_source);
 468   isl_union_map_compute_flow (isl_union_map_copy (all_writes),
 469                               reads, empty,
 470                               isl_union_map_copy (original),
 471                               must_war, may_war, must_war_no_source,
 472                               may_war_no_source);
 473   isl_union_map_compute_flow (all_writes, must_writes, may_writes,
 474                               original,
 475                               must_waw, may_waw, must_waw_no_source,
 476                               may_waw_no_source);
 477 }
 478
 479 isl_union_map *
 480 scop_get_dependences (scop_p scop)
 481 {
 482   if (scop->dependence)
 483     return scop->dependence;
 484
 485   /* The original dependence relations:
 486      RAW are read after write dependences,
 487      WAR are write after read dependences,
 488      WAW are write after write dependences.  */
 489   isl_union_map *must_raw = NULL, *may_raw = NULL, *must_raw_no_source = NULL,
 490       *may_raw_no_source = NULL, *must_war = NULL, *may_war = NULL,
 491       *must_war_no_source = NULL, *may_war_no_source = NULL, *must_waw = NULL,
 492       *may_waw = NULL, *must_waw_no_source = NULL, *may_waw_no_source = NULL;
 493
 494   compute_deps (scop, scop->pbbs,
 495                   &must_raw, &may_raw,
 496                   &must_raw_no_source, &may_raw_no_source,
 497                   &must_war, &may_war,
 498                   &must_war_no_source, &may_war_no_source,
 499                   &must_waw, &may_waw,
 500                   &must_waw_no_source, &may_waw_no_source);
 501
 502   isl_union_map *dependences = must_raw;
 503   dependences = isl_union_map_union (dependences, must_war);
 504   dependences = isl_union_map_union (dependences, must_waw);
 505   dependences = isl_union_map_union (dependences, may_raw);
 506   dependences = isl_union_map_union (dependences, may_war);
 507   dependences = isl_union_map_union (dependences, may_waw);
 508   dependences = isl_union_map_coalesce (dependences);
 509
 510   if (dump_file)
 511     {
 512       fprintf (dump_file, "data dependences (\n");
 513       print_isl_union_map (dump_file, dependences);
 514       fprintf (dump_file, ")\n");
 515     }
 516
 517   isl_union_map_free (must_raw_no_source);
 518   isl_union_map_free (may_raw_no_source);
 519   isl_union_map_free (must_war_no_source);
 520   isl_union_map_free (may_war_no_source);
 521   isl_union_map_free (must_waw_no_source);
 522   isl_union_map_free (may_waw_no_source);
 523
 524   scop->dependence = dependences;
 525   return dependences;
 526 }
 527
 528 #endif /* HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS */
 529
 530 #endif /* HAVE_isl */