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 /* Helper function used on each MAP of a isl_union_map.  Computes the
 172    maximal output dimension.  */
 173
 174 static isl_stat
 175 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
 176 {
 177   int global_max = *((int *) user);
 178   isl_space *space = isl_map_get_space (map);
 179   int nb_out = isl_space_dim (space, isl_dim_out);
 180
 181   if (global_max < nb_out)
 182     *((int *) user) = nb_out;
 183
 184   isl_map_free (map);
 185   isl_space_free (space);
 186   return isl_stat_ok;
 187 }
 188
 189 /* Extends the output dimension of MAP to MAX dimensions.  */
 190
 191 static __isl_give isl_map *
 192 extend_map (__isl_take isl_map *map, int max)
 193 {
 194   isl_space *space = isl_map_get_space (map);
 195   int n = isl_space_dim (space, isl_dim_out);
 196
 197   isl_space_free (space);
 198   return isl_map_add_dims (map, isl_dim_out, max - n);
 199 }
 200
 201 /* Structure used to pass parameters to extend_schedule_1.  */
 202
 203 struct extend_schedule_str {
 204   int max;
 205   isl_union_map *umap;
 206 };
 207
 208 /* Helper function for extend_schedule.  */
 209
 210 static isl_stat
 211 extend_schedule_1 (__isl_take isl_map *map, void *user)
 212 {
 213   struct extend_schedule_str *str = (struct extend_schedule_str *) user;
 214   str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
 215   return isl_stat_ok;
 216 }
 217
 218 /* Return a relation that has uniform output dimensions.  */
 219
 220 static __isl_give isl_union_map *
 221 extend_schedule (__isl_take isl_union_map *x)
 222 {
 223   int max = 0;
 224   struct extend_schedule_str str;
 225
 226   isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
 227   str.max = max;
 228   str.umap = isl_union_map_empty (isl_union_map_get_space (x));
 229   isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
 230   isl_union_map_free (x);
 231   return isl_union_map_coalesce (str.umap);
 232 }
 233
 234 /* Applies SCHEDULE to the in and out dimensions of the dependences
 235    DEPS and return the resulting relation.  */
 236
 237 static isl_map *
 238 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
 239                         __isl_keep isl_union_map *deps)
 240 {
 241   isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
 242   isl_union_map *ux = isl_union_map_copy (deps);
 243   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
 244   ux = isl_union_map_apply_range (ux, trans);
 245   ux = isl_union_map_coalesce (ux);
 246
 247   if (!isl_union_map_is_empty (ux))
 248     return isl_map_from_union_map (ux);
 249
 250   isl_union_map_free (ux);
 251   return NULL;
 252 }
 253
 254 /* Return true when DEPS is non empty and the intersection of LEX with
 255    the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
 256    in which all the inputs before DEPTH occur at the same time as the
 257    output, and the input at DEPTH occurs before output.  */
 258
 259 bool
 260 carries_deps (__isl_keep isl_union_map *schedule,
 261               __isl_keep isl_union_map *deps,
 262               int depth)
 263 {
 264   if (isl_union_map_is_empty (deps))
 265     return false;
 266
 267   isl_map *x = apply_schedule_on_deps (schedule, deps);
 268   if (x == NULL)
 269     return false;
 270
 271   isl_space *space = isl_map_get_space (x);
 272   isl_map *lex = isl_map_lex_le (isl_space_range (space));
 273   isl_constraint *ineq = isl_inequality_alloc
 274     (isl_local_space_from_space (isl_map_get_space (x)));
 275
 276   for (int i = 0; i < depth - 1; i++)
 277     lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
 278
 279   /* in + 1 <= out  */
 280   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
 281   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
 282   ineq = isl_constraint_set_constant_si (ineq, -1);
 283   lex = isl_map_add_constraint (lex, ineq);
 284   lex = isl_map_coalesce (lex);
 285   x = isl_map_intersect (x, lex);
 286   bool res = !isl_map_is_empty (x);
 287
 288   isl_map_free (x);
 289   return res;
 290 }
 291
 292 /* Compute the dependence relations for the SCOP:
 293    RAW are read after write dependences,
 294    WAR are write after read dependences,
 295    WAW are write after write dependences.  */
 296
 297 void
 298 scop_get_dependences (scop_p scop)
 299 {
 300   if (scop->dependence)
 301     return;
 302
 303   isl_union_map *reads = scop_get_reads (scop);
 304   isl_union_map *must_writes = scop_get_must_writes (scop);
 305   isl_union_map *may_writes = scop_get_may_writes (scop);
 306
 307   if (dump_file)
 308     {
 309       fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
 310       fprintf (dump_file, "Statements on the iteration domain are mapped to"
 311                " array references.\n");
 312       fprintf (dump_file, "  To read the following data references:\n\n");
 313       fprintf (dump_file, "  S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
 314       fprintf (dump_file, "  S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
 315
 316       fprintf (dump_file, "  S_5[i0] is the dynamic instance of statement"
 317                " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
 318       fprintf (dump_file, "  [1, i0] is a 'memref' with alias set 1"
 319                " and first subscript access i0.\n");
 320       fprintf (dump_file, "  [106] is a 'scalar reference' which is the sum of"
 321                " SSA_NAME_VERSION 6"
 322                " and --param graphite-max-arrays-per-scop=100\n");
 323       fprintf (dump_file, "-----------------------\n\n");
 324
 325       fprintf (dump_file, "data references (\n");
 326       fprintf (dump_file, "  reads: ");
 327       print_isl_union_map (dump_file, reads);
 328       fprintf (dump_file, "  must_writes: ");
 329       print_isl_union_map (dump_file, must_writes);
 330       fprintf (dump_file, "  may_writes: ");
 331       print_isl_union_map (dump_file, may_writes);
 332       fprintf (dump_file, ")\n");
 333     }
 334
 335   gcc_assert (scop->original_schedule);
 336
 337   isl_union_access_info *ai;
 338   ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
 339   ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
 340   ai = isl_union_access_info_set_may_source (ai, may_writes);
 341   ai = isl_union_access_info_set_schedule
 342     (ai, isl_schedule_copy (scop->original_schedule));
 343   isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
 344   isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
 345   isl_union_flow_free (flow);
 346
 347   ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
 348   ai = isl_union_access_info_set_must_source (ai, must_writes);
 349   ai = isl_union_access_info_set_may_source (ai, reads);
 350   ai = isl_union_access_info_set_schedule
 351     (ai, isl_schedule_copy (scop->original_schedule));
 352   flow = isl_union_access_info_compute_flow (ai);
 353
 354   isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
 355   isl_union_map *war = isl_union_flow_get_may_dependence (flow);
 356   war = isl_union_map_subtract (war, isl_union_map_copy (waw));
 357   isl_union_flow_free (flow);
 358
 359   raw = isl_union_map_coalesce (raw);
 360   waw = isl_union_map_coalesce (waw);
 361   war = isl_union_map_coalesce (war);
 362
 363   isl_union_map *dependences = raw;
 364   dependences = isl_union_map_union (dependences, war);
 365   dependences = isl_union_map_union (dependences, waw);
 366   dependences = isl_union_map_coalesce (dependences);
 367
 368   if (dump_file)
 369     {
 370       fprintf (dump_file, "data dependences (\n");
 371       print_isl_union_map (dump_file, dependences);
 372       fprintf (dump_file, ")\n");
 373     }
 374
 375   scop->dependence = dependences;
 376 }
 377
 378 #endif /* HAVE_isl */