1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009-2018 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 *
constrain_domain(isl_map * map,isl_set * s)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 *
add_pdr_constraints(poly_dr_p pdr,poly_bb_p pbb)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 an isl description of all memory operations in SCOP. The memory
67 reads are returned in READS and writes in MUST_WRITES and MAY_WRITES. */
68
69 static void
scop_get_reads_and_writes(scop_p scop,isl_union_map * & reads,isl_union_map * & must_writes,isl_union_map * & may_writes)70 scop_get_reads_and_writes (scop_p scop, isl_union_map *&reads,
71 isl_union_map *&must_writes,
72 isl_union_map *&may_writes)
73 {
74 int i, j;
75 poly_bb_p pbb;
76 poly_dr_p pdr;
77
78 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
79 {
80 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) {
81 if (pdr_read_p (pdr))
82 {
83 if (dump_file)
84 {
85 fprintf (dump_file, "Adding read to depedence graph: ");
86 print_pdr (dump_file, pdr);
87 }
88 isl_union_map *um
89 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
90 reads = isl_union_map_union (reads, um);
91 if (dump_file)
92 {
93 fprintf (dump_file, "Reads depedence graph: ");
94 print_isl_union_map (dump_file, reads);
95 }
96 }
97 else if (pdr_write_p (pdr))
98 {
99 if (dump_file)
100 {
101 fprintf (dump_file, "Adding must write to depedence graph: ");
102 print_pdr (dump_file, pdr);
103 }
104 isl_union_map *um
105 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
106 must_writes = isl_union_map_union (must_writes, um);
107 if (dump_file)
108 {
109 fprintf (dump_file, "Must writes depedence graph: ");
110 print_isl_union_map (dump_file, must_writes);
111 }
112 }
113 else if (pdr_may_write_p (pdr))
114 {
115 if (dump_file)
116 {
117 fprintf (dump_file, "Adding may write to depedence graph: ");
118 print_pdr (dump_file, pdr);
119 }
120 isl_union_map *um
121 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
122 may_writes = isl_union_map_union (may_writes, um);
123 if (dump_file)
124 {
125 fprintf (dump_file, "May writes depedence graph: ");
126 print_isl_union_map (dump_file, may_writes);
127 }
128 }
129 }
130 }
131 }
132
133 /* Helper function used on each MAP of a isl_union_map. Computes the
134 maximal output dimension. */
135
136 static isl_stat
max_number_of_out_dimensions(__isl_take isl_map * map,void * user)137 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
138 {
139 int global_max = *((int *) user);
140 isl_space *space = isl_map_get_space (map);
141 int nb_out = isl_space_dim (space, isl_dim_out);
142
143 if (global_max < nb_out)
144 *((int *) user) = nb_out;
145
146 isl_map_free (map);
147 isl_space_free (space);
148 return isl_stat_ok;
149 }
150
151 /* Extends the output dimension of MAP to MAX dimensions. */
152
153 static __isl_give isl_map *
extend_map(__isl_take isl_map * map,int max)154 extend_map (__isl_take isl_map *map, int max)
155 {
156 isl_space *space = isl_map_get_space (map);
157 int n = isl_space_dim (space, isl_dim_out);
158
159 isl_space_free (space);
160 return isl_map_add_dims (map, isl_dim_out, max - n);
161 }
162
163 /* Structure used to pass parameters to extend_schedule_1. */
164
165 struct extend_schedule_str {
166 int max;
167 isl_union_map *umap;
168 };
169
170 /* Helper function for extend_schedule. */
171
172 static isl_stat
extend_schedule_1(__isl_take isl_map * map,void * user)173 extend_schedule_1 (__isl_take isl_map *map, void *user)
174 {
175 struct extend_schedule_str *str = (struct extend_schedule_str *) user;
176 str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
177 return isl_stat_ok;
178 }
179
180 /* Return a relation that has uniform output dimensions. */
181
182 static __isl_give isl_union_map *
extend_schedule(__isl_take isl_union_map * x)183 extend_schedule (__isl_take isl_union_map *x)
184 {
185 int max = 0;
186 struct extend_schedule_str str;
187
188 isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
189 str.max = max;
190 str.umap = isl_union_map_empty (isl_union_map_get_space (x));
191 isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
192 isl_union_map_free (x);
193 return isl_union_map_coalesce (str.umap);
194 }
195
196 /* Applies SCHEDULE to the in and out dimensions of the dependences
197 DEPS and return the resulting relation. */
198
199 static isl_map *
apply_schedule_on_deps(__isl_keep isl_union_map * schedule,__isl_keep isl_union_map * deps)200 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
201 __isl_keep isl_union_map *deps)
202 {
203 isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
204 isl_union_map *ux = isl_union_map_copy (deps);
205 ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
206 ux = isl_union_map_apply_range (ux, trans);
207 ux = isl_union_map_coalesce (ux);
208
209 if (!isl_union_map_is_empty (ux))
210 return isl_map_from_union_map (ux);
211
212 isl_union_map_free (ux);
213 return NULL;
214 }
215
216 /* Return true when DEPS is non empty and the intersection of LEX with
217 the DEPS transformed by SCHEDULE is non empty. LEX is the relation
218 in which all the inputs before DEPTH occur at the same time as the
219 output, and the input at DEPTH occurs before output. */
220
221 bool
carries_deps(__isl_keep isl_union_map * schedule,__isl_keep isl_union_map * deps,int depth)222 carries_deps (__isl_keep isl_union_map *schedule,
223 __isl_keep isl_union_map *deps,
224 int depth)
225 {
226 if (isl_union_map_is_empty (deps))
227 return false;
228
229 isl_map *x = apply_schedule_on_deps (schedule, deps);
230 if (x == NULL)
231 return false;
232
233 isl_space *space = isl_map_get_space (x);
234 isl_map *lex = isl_map_lex_le (isl_space_range (space));
235 isl_constraint *ineq = isl_inequality_alloc
236 (isl_local_space_from_space (isl_map_get_space (x)));
237
238 for (int i = 0; i < depth - 1; i++)
239 lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
240
241 /* in + 1 <= out */
242 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
243 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
244 ineq = isl_constraint_set_constant_si (ineq, -1);
245 lex = isl_map_add_constraint (lex, ineq);
246 lex = isl_map_coalesce (lex);
247 x = isl_map_intersect (x, lex);
248 bool res = !isl_map_is_empty (x);
249
250 isl_map_free (x);
251 return res;
252 }
253
254 /* Compute the dependence relations for the SCOP:
255 RAW are read after write dependences,
256 WAR are write after read dependences,
257 WAW are write after write dependences. */
258
259 void
scop_get_dependences(scop_p scop)260 scop_get_dependences (scop_p scop)
261 {
262 if (scop->dependence)
263 return;
264
265 isl_space *space = isl_set_get_space (scop->param_context);
266 isl_union_map *reads = isl_union_map_empty (isl_space_copy (space));
267 isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space));
268 isl_union_map *may_writes = isl_union_map_empty (space);
269 scop_get_reads_and_writes (scop, reads, must_writes, may_writes);
270
271 if (dump_file)
272 {
273 fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
274 fprintf (dump_file, "Statements on the iteration domain are mapped to"
275 " array references.\n");
276 fprintf (dump_file, " To read the following data references:\n\n");
277 fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
278 fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
279
280 fprintf (dump_file, " S_5[i0] is the dynamic instance of statement"
281 " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
282 fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1"
283 " and first subscript access i0.\n");
284 fprintf (dump_file, " [106] is a 'scalar reference' which is the sum of"
285 " SSA_NAME_VERSION 6"
286 " and --param graphite-max-arrays-per-scop=100\n");
287 fprintf (dump_file, "-----------------------\n\n");
288
289 fprintf (dump_file, "data references (\n");
290 fprintf (dump_file, " reads: ");
291 print_isl_union_map (dump_file, reads);
292 fprintf (dump_file, " must_writes: ");
293 print_isl_union_map (dump_file, must_writes);
294 fprintf (dump_file, " may_writes: ");
295 print_isl_union_map (dump_file, may_writes);
296 fprintf (dump_file, ")\n");
297 }
298
299 gcc_assert (scop->original_schedule);
300
301 isl_union_access_info *ai;
302 ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
303 ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
304 ai = isl_union_access_info_set_may_source (ai, may_writes);
305 ai = isl_union_access_info_set_schedule
306 (ai, isl_schedule_copy (scop->original_schedule));
307 isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
308 isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
309 isl_union_flow_free (flow);
310
311 ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
312 ai = isl_union_access_info_set_must_source (ai, must_writes);
313 ai = isl_union_access_info_set_may_source (ai, reads);
314 ai = isl_union_access_info_set_schedule
315 (ai, isl_schedule_copy (scop->original_schedule));
316 flow = isl_union_access_info_compute_flow (ai);
317
318 isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
319 isl_union_map *war = isl_union_flow_get_may_dependence (flow);
320 war = isl_union_map_subtract (war, isl_union_map_copy (waw));
321 isl_union_flow_free (flow);
322
323 raw = isl_union_map_coalesce (raw);
324 waw = isl_union_map_coalesce (waw);
325 war = isl_union_map_coalesce (war);
326
327 isl_union_map *dependences = raw;
328 dependences = isl_union_map_union (dependences, war);
329 dependences = isl_union_map_union (dependences, waw);
330 dependences = isl_union_map_coalesce (dependences);
331
332 if (dump_file)
333 {
334 fprintf (dump_file, "data dependences (\n");
335 print_isl_union_map (dump_file, dependences);
336 fprintf (dump_file, ")\n");
337 }
338
339 scop->dependence = dependences;
340 }
341
342 #endif /* HAVE_isl */
343