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