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/constraint.h>
  29 #include <isl/set.h>
  30 #include <isl/map.h>
  31 #include <isl/union_map.h>
  32 #include <isl/flow.h>
  33 #include <isl/constraint.h>
  34
  35 #include "system.h"
  36 #include "coretypes.h"
  37 #include "backend.h"
  38 #include "cfghooks.h"
  39 #include "tree.h"
  40 #include "gimple.h"
  41 #include "fold-const.h"
  42 #include "gimple-iterator.h"
  43 #include "tree-ssa-loop.h"
  44 #include "tree-pass.h"
  45 #include "cfgloop.h"
  46 #include "tree-data-ref.h"
  47 #include "graphite-poly.h"
  48
  49
  50 /* Add the constraints from the set S to the domain of MAP.  */
  51
  52 static isl_map *
  53 constrain_domain (isl_map *map, isl_set *s)
  54 {
  55   isl_space *d = isl_map_get_space (map);
  56   isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
  57
  58   s = isl_set_set_tuple_id (s, id);
  59   isl_space_free (d);
  60   return isl_map_intersect_domain (map, s);
  61 }
  62
  63 /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain.  */
  64
  65 static isl_map *
  66 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
  67 {
  68   isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
  69                                         isl_set_copy (pdr->subscript_sizes));
  70   x = constrain_domain (x, isl_set_copy (pbb->domain));
  71   return x;
  72 }
  73
  74 /* Returns all the memory reads in SCOP.  */
  75
  76 static isl_union_map *
  77 scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
  78 {
  79   int i, j;
  80   poly_bb_p pbb;
  81   poly_dr_p pdr;
  82   isl_space *space = isl_set_get_space (scop->param_context);
  83   isl_union_map *res = isl_union_map_empty (space);
  84
  85   FOR_EACH_VEC_ELT (pbbs, i, pbb)
  86     {
  87       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
  88         if (pdr_read_p (pdr))
  89           res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
  90     }
  91
  92   return res;
  93 }
  94
  95 /* Returns all the memory must writes in SCOP.  */
  96
  97 static isl_union_map *
  98 scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
  99 {
 100   int i, j;
 101   poly_bb_p pbb;
 102   poly_dr_p pdr;
 103   isl_space *space = isl_set_get_space (scop->param_context);
 104   isl_union_map *res = isl_union_map_empty (space);
 105
 106   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 107     {
 108       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 109         if (pdr_write_p (pdr))
 110           res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
 111     }
 112
 113   return res;
 114 }
 115
 116 /* Returns all the memory may writes in SCOP.  */
 117
 118 static isl_union_map *
 119 scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
 120 {
 121   int i, j;
 122   poly_bb_p pbb;
 123   poly_dr_p pdr;
 124   isl_space *space = isl_set_get_space (scop->param_context);
 125   isl_union_map *res = isl_union_map_empty (space);
 126
 127   FOR_EACH_VEC_ELT (pbbs, i, pbb)
 128     {
 129       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 130         if (pdr_may_write_p (pdr))
 131           res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
 132     }
 133
 134   return res;
 135 }
 136
 137 /* Returns all the original schedules in SCOP.  */
 138
 139 static isl_union_map *
 140 scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
 141 {
 142   int i;
 143   poly_bb_p pbb;
 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 (pbbs, i, pbb)
 148     {
 149       res = isl_union_map_add_map
 150         (res, constrain_domain (isl_map_copy (pbb->schedule),
 151                                 isl_set_copy (pbb->domain)));
 152     }
 153
 154   return res;
 155 }
 156
 157 /* Helper function used on each MAP of a isl_union_map.  Computes the
 158    maximal output dimension.  */
 159
 160 static isl_stat
 161 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
 162 {
 163   int global_max = *((int *) user);
 164   isl_space *space = isl_map_get_space (map);
 165   int nb_out = isl_space_dim (space, isl_dim_out);
 166
 167   if (global_max < nb_out)
 168     *((int *) user) = nb_out;
 169
 170   isl_map_free (map);
 171   isl_space_free (space);
 172   return isl_stat_ok;
 173 }
 174
 175 /* Extends the output dimension of MAP to MAX dimensions.  */
 176
 177 static __isl_give isl_map *
 178 extend_map (__isl_take isl_map *map, int max)
 179 {
 180   isl_space *space = isl_map_get_space (map);
 181   int n = isl_space_dim (space, isl_dim_out);
 182
 183   isl_space_free (space);
 184   return isl_map_add_dims (map, isl_dim_out, max - n);
 185 }
 186
 187 /* Structure used to pass parameters to extend_schedule_1.  */
 188
 189 struct extend_schedule_str {
 190   int max;
 191   isl_union_map *umap;
 192 };
 193
 194 /* Helper function for extend_schedule.  */
 195
 196 static isl_stat
 197 extend_schedule_1 (__isl_take isl_map *map, void *user)
 198 {
 199   struct extend_schedule_str *str = (struct extend_schedule_str *) user;
 200   str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
 201   return isl_stat_ok;
 202 }
 203
 204 /* Return a relation that has uniform output dimensions.  */
 205
 206 static __isl_give isl_union_map *
 207 extend_schedule (__isl_take isl_union_map *x)
 208 {
 209   int max = 0;
 210   struct extend_schedule_str str;
 211
 212   isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
 213   str.max = max;
 214   str.umap = isl_union_map_empty (isl_union_map_get_space (x));
 215   isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
 216   isl_union_map_free (x);
 217   return str.umap;
 218 }
 219
 220 /* Applies SCHEDULE to the in and out dimensions of the dependences
 221    DEPS and return the resulting relation.  */
 222
 223 static isl_map *
 224 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
 225                         __isl_keep isl_union_map *deps)
 226 {
 227   isl_map *x;
 228   isl_union_map *ux, *trans;
 229
 230   trans = isl_union_map_copy (schedule);
 231   trans = extend_schedule (trans);
 232   ux = isl_union_map_copy (deps);
 233   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
 234   ux = isl_union_map_apply_range (ux, trans);
 235   if (isl_union_map_is_empty (ux))
 236     {
 237       isl_union_map_free (ux);
 238       return NULL;
 239     }
 240   x = isl_map_from_union_map (ux);
 241
 242   return x;
 243 }
 244
 245 /* Return true when DEPS is non empty and the intersection of LEX with
 246    the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
 247    in which all the inputs before DEPTH occur at the same time as the
 248    output, and the input at DEPTH occurs before output.  */
 249
 250 bool
 251 carries_deps (__isl_keep isl_union_map *schedule,
 252               __isl_keep isl_union_map *deps,
 253               int depth)
 254 {
 255   bool res;
 256   int i;
 257   isl_space *space;
 258   isl_map *lex, *x;
 259   isl_constraint *ineq;
 260
 261   if (isl_union_map_is_empty (deps))
 262     return false;
 263
 264   x = apply_schedule_on_deps (schedule, deps);
 265   if (x == NULL)
 266     return false;
 267   space = isl_map_get_space (x);
 268   space = isl_space_range (space);
 269   lex = isl_map_lex_le (space);
 270   space = isl_map_get_space (x);
 271   ineq = isl_inequality_alloc (isl_local_space_from_space (space));
 272
 273   for (i = 0; i < depth - 1; i++)
 274     lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
 275
 276   /* in + 1 <= out  */
 277   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
 278   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
 279   ineq = isl_constraint_set_constant_si (ineq, -1);
 280   lex = isl_map_add_constraint (lex, ineq);
 281   x = isl_map_intersect (x, lex);
 282   res = !isl_map_is_empty (x);
 283
 284   isl_map_free (x);
 285   return res;
 286 }
 287
 288 /* Compute the original data dependences in SCOP for all the reads and
 289    writes in PBBS.  */
 290
 291 static void
 292 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
 293               isl_union_map **must_raw,
 294               isl_union_map **may_raw,
 295               isl_union_map **must_raw_no_source,
 296               isl_union_map **may_raw_no_source,
 297               isl_union_map **must_war,
 298               isl_union_map **may_war,
 299               isl_union_map **must_war_no_source,
 300               isl_union_map **may_war_no_source,
 301               isl_union_map **must_waw,
 302               isl_union_map **may_waw,
 303               isl_union_map **must_waw_no_source,
 304               isl_union_map **may_waw_no_source)
 305 {
 306   isl_union_map *reads = scop_get_reads (scop, pbbs);
 307   isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
 308   isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
 309   isl_union_map *all_writes = isl_union_map_union
 310     (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
 311   isl_space *space = isl_union_map_get_space (all_writes);
 312   isl_union_map *empty = isl_union_map_empty (space);
 313   isl_union_map *original = scop_get_original_schedule (scop, pbbs);
 314
 315   isl_union_map_compute_flow (isl_union_map_copy (reads),
 316                               isl_union_map_copy (must_writes),
 317                               isl_union_map_copy (may_writes),
 318                               isl_union_map_copy (original),
 319                               must_raw, may_raw, must_raw_no_source,
 320                               may_raw_no_source);
 321   isl_union_map_compute_flow (isl_union_map_copy (all_writes),
 322                               reads, empty,
 323                               isl_union_map_copy (original),
 324                               must_war, may_war, must_war_no_source,
 325                               may_war_no_source);
 326   isl_union_map_compute_flow (all_writes, must_writes, may_writes,
 327                               original,
 328                               must_waw, may_waw, must_waw_no_source,
 329                               may_waw_no_source);
 330 }
 331
 332 isl_union_map *
 333 scop_get_dependences (scop_p scop)
 334 {
 335   isl_union_map *dependences;
 336
 337   if (!scop->must_raw)
 338     compute_deps (scop, scop->pbbs,
 339                   &scop->must_raw, &scop->may_raw,
 340                   &scop->must_raw_no_source, &scop->may_raw_no_source,
 341                   &scop->must_war, &scop->may_war,
 342                   &scop->must_war_no_source, &scop->may_war_no_source,
 343                   &scop->must_waw, &scop->may_waw,
 344                   &scop->must_waw_no_source, &scop->may_waw_no_source);
 345
 346   dependences = isl_union_map_copy (scop->must_raw);
 347   dependences = isl_union_map_union (dependences,
 348                                      isl_union_map_copy (scop->must_war));
 349   dependences = isl_union_map_union (dependences,
 350                                      isl_union_map_copy (scop->must_waw));
 351   dependences = isl_union_map_union (dependences,
 352                                      isl_union_map_copy (scop->may_raw));
 353   dependences = isl_union_map_union (dependences,
 354                                      isl_union_map_copy (scop->may_war));
 355   dependences = isl_union_map_union (dependences,
 356                                      isl_union_map_copy (scop->may_waw));
 357
 358   if (dump_file)
 359     {
 360       fprintf (dump_file, "data dependences (\n");
 361       print_isl_union_map (dump_file, dependences);
 362       fprintf (dump_file, ")\n");
 363     }
 364
 365   return dependences;
 366 }
 367
 368 #endif /* HAVE_isl */