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