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