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 */ 379