Branch data Line data Source code
1 : : /* Data dependence analysis for Graphite.
2 : : Copyright (C) 2009-2024 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 INCLUDE_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 : 1388 : constrain_domain (isl_map *map, isl_set *s)
46 : : {
47 : 1388 : isl_space *d = isl_map_get_space (map);
48 : 1388 : isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
49 : :
50 : 1388 : s = isl_set_set_tuple_id (s, id);
51 : 1388 : isl_space_free (d);
52 : 1388 : 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 : 1388 : add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
59 : : {
60 : 1388 : isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
61 : : isl_set_copy (pdr->subscript_sizes));
62 : 1388 : x = isl_map_coalesce (x);
63 : 1388 : 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
70 : 126 : 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 : 126 : int i, j;
75 : 126 : poly_bb_p pbb;
76 : 126 : poly_dr_p pdr;
77 : :
78 : 920 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
79 : : {
80 : 2182 : FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) {
81 : 1388 : if (pdr_read_p (pdr))
82 : : {
83 : 633 : if (dump_file)
84 : : {
85 : 333 : fprintf (dump_file, "Adding read to depedence graph: ");
86 : 333 : print_pdr (dump_file, pdr);
87 : : }
88 : 633 : isl_union_map *um
89 : 633 : = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
90 : 633 : reads = isl_union_map_union (reads, um);
91 : 633 : if (dump_file)
92 : : {
93 : 333 : fprintf (dump_file, "Reads depedence graph: ");
94 : 333 : print_isl_union_map (dump_file, reads);
95 : : }
96 : : }
97 : 755 : else if (pdr_write_p (pdr))
98 : : {
99 : 755 : if (dump_file)
100 : : {
101 : 413 : fprintf (dump_file, "Adding must write to depedence graph: ");
102 : 413 : print_pdr (dump_file, pdr);
103 : : }
104 : 755 : isl_union_map *um
105 : 755 : = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
106 : 755 : must_writes = isl_union_map_union (must_writes, um);
107 : 755 : if (dump_file)
108 : : {
109 : 413 : fprintf (dump_file, "Must writes depedence graph: ");
110 : 413 : print_isl_union_map (dump_file, must_writes);
111 : : }
112 : : }
113 : 0 : else if (pdr_may_write_p (pdr))
114 : : {
115 : 0 : if (dump_file)
116 : : {
117 : 0 : fprintf (dump_file, "Adding may write to depedence graph: ");
118 : 0 : print_pdr (dump_file, pdr);
119 : : }
120 : 0 : isl_union_map *um
121 : 0 : = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
122 : 0 : may_writes = isl_union_map_union (may_writes, um);
123 : 0 : if (dump_file)
124 : : {
125 : 0 : fprintf (dump_file, "May writes depedence graph: ");
126 : 0 : print_isl_union_map (dump_file, may_writes);
127 : : }
128 : : }
129 : : }
130 : : }
131 : 126 : }
132 : :
133 : : /* Helper function used on each MAP of a isl_union_map. Computes the
134 : : maximal output dimension. */
135 : :
136 : : static isl_stat
137 : 62 : max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
138 : : {
139 : 62 : int global_max = *((int *) user);
140 : 62 : isl_space *space = isl_map_get_space (map);
141 : 62 : int nb_out = isl_space_dim (space, isl_dim_out);
142 : :
143 : 62 : if (global_max < nb_out)
144 : 51 : *((int *) user) = nb_out;
145 : :
146 : 62 : isl_map_free (map);
147 : 62 : isl_space_free (space);
148 : 62 : return isl_stat_ok;
149 : : }
150 : :
151 : : /* Extends the output dimension of MAP to MAX dimensions. */
152 : :
153 : : static __isl_give isl_map *
154 : 62 : extend_map (__isl_take isl_map *map, int max)
155 : : {
156 : 62 : isl_space *space = isl_map_get_space (map);
157 : 62 : int n = isl_space_dim (space, isl_dim_out);
158 : :
159 : 62 : isl_space_free (space);
160 : 62 : 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
173 : 62 : extend_schedule_1 (__isl_take isl_map *map, void *user)
174 : : {
175 : 62 : struct extend_schedule_str *str = (struct extend_schedule_str *) user;
176 : 62 : str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
177 : 62 : return isl_stat_ok;
178 : : }
179 : :
180 : : /* Return a relation that has uniform output dimensions. */
181 : :
182 : : static __isl_give isl_union_map *
183 : 51 : extend_schedule (__isl_take isl_union_map *x)
184 : : {
185 : 51 : int max = 0;
186 : 51 : struct extend_schedule_str str;
187 : :
188 : 51 : isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
189 : 51 : str.max = max;
190 : 51 : str.umap = isl_union_map_empty (isl_union_map_get_space (x));
191 : 51 : isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
192 : 51 : isl_union_map_free (x);
193 : 51 : 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 *
200 : 51 : apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
201 : : __isl_keep isl_union_map *deps)
202 : : {
203 : 51 : isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
204 : 51 : isl_union_map *ux = isl_union_map_copy (deps);
205 : 51 : ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
206 : 51 : ux = isl_union_map_apply_range (ux, trans);
207 : 51 : ux = isl_union_map_coalesce (ux);
208 : :
209 : 51 : if (!isl_union_map_is_empty (ux))
210 : 26 : return isl_map_from_union_map (ux);
211 : :
212 : 25 : isl_union_map_free (ux);
213 : 25 : 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
222 : 53 : carries_deps (__isl_keep isl_union_map *schedule,
223 : : __isl_keep isl_union_map *deps,
224 : : int depth)
225 : : {
226 : 53 : if (isl_union_map_is_empty (deps))
227 : : return false;
228 : :
229 : 51 : isl_map *x = apply_schedule_on_deps (schedule, deps);
230 : 51 : if (x == NULL)
231 : : return false;
232 : :
233 : 26 : isl_space *space = isl_map_get_space (x);
234 : 26 : isl_map *lex = isl_map_lex_le (isl_space_range (space));
235 : 26 : isl_constraint *ineq = isl_inequality_alloc
236 : 26 : (isl_local_space_from_space (isl_map_get_space (x)));
237 : :
238 : 43 : for (int i = 0; i < depth - 1; i++)
239 : 17 : lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
240 : :
241 : : /* in + 1 <= out */
242 : 26 : ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
243 : 26 : ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
244 : 26 : ineq = isl_constraint_set_constant_si (ineq, -1);
245 : 26 : lex = isl_map_add_constraint (lex, ineq);
246 : 26 : lex = isl_map_coalesce (lex);
247 : 26 : x = isl_map_intersect (x, lex);
248 : 26 : bool res = !isl_map_is_empty (x);
249 : :
250 : 26 : isl_map_free (x);
251 : 26 : 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
260 : 126 : scop_get_dependences (scop_p scop)
261 : : {
262 : 126 : if (scop->dependence)
263 : 0 : return;
264 : :
265 : 126 : isl_space *space = isl_set_get_space (scop->param_context);
266 : 126 : isl_union_map *reads = isl_union_map_empty (isl_space_copy (space));
267 : 126 : isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space));
268 : 126 : isl_union_map *may_writes = isl_union_map_empty (space);
269 : 126 : scop_get_reads_and_writes (scop, reads, must_writes, may_writes);
270 : :
271 : 126 : if (dump_file)
272 : : {
273 : 61 : fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
274 : 61 : fprintf (dump_file, "Statements on the iteration domain are mapped to"
275 : : " array references.\n");
276 : 61 : fprintf (dump_file, " To read the following data references:\n\n");
277 : 61 : fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
278 : 61 : fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
279 : :
280 : 61 : 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 : 61 : fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1"
283 : : " and first subscript access i0.\n");
284 : 61 : 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 : 61 : fprintf (dump_file, "-----------------------\n\n");
288 : :
289 : 61 : fprintf (dump_file, "data references (\n");
290 : 61 : fprintf (dump_file, " reads: ");
291 : 61 : print_isl_union_map (dump_file, reads);
292 : 61 : fprintf (dump_file, " must_writes: ");
293 : 61 : print_isl_union_map (dump_file, must_writes);
294 : 61 : fprintf (dump_file, " may_writes: ");
295 : 61 : print_isl_union_map (dump_file, may_writes);
296 : 61 : fprintf (dump_file, ")\n");
297 : : }
298 : :
299 : 126 : gcc_assert (scop->original_schedule);
300 : :
301 : 126 : isl_union_access_info *ai;
302 : 126 : ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
303 : 126 : ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
304 : 126 : ai = isl_union_access_info_set_may_source (ai, may_writes);
305 : 126 : ai = isl_union_access_info_set_schedule
306 : 126 : (ai, isl_schedule_copy (scop->original_schedule));
307 : 126 : isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
308 : 126 : isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
309 : 126 : isl_union_flow_free (flow);
310 : :
311 : 126 : ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
312 : 126 : ai = isl_union_access_info_set_must_source (ai, must_writes);
313 : 126 : ai = isl_union_access_info_set_may_source (ai, reads);
314 : 126 : ai = isl_union_access_info_set_schedule
315 : 126 : (ai, isl_schedule_copy (scop->original_schedule));
316 : 126 : flow = isl_union_access_info_compute_flow (ai);
317 : :
318 : 126 : isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
319 : 126 : isl_union_map *war = isl_union_flow_get_may_dependence (flow);
320 : 126 : war = isl_union_map_subtract (war, isl_union_map_copy (waw));
321 : 126 : isl_union_flow_free (flow);
322 : :
323 : 126 : raw = isl_union_map_coalesce (raw);
324 : 126 : waw = isl_union_map_coalesce (waw);
325 : 126 : war = isl_union_map_coalesce (war);
326 : :
327 : 126 : isl_union_map *dependences = raw;
328 : 126 : dependences = isl_union_map_union (dependences, war);
329 : 126 : dependences = isl_union_map_union (dependences, waw);
330 : 126 : dependences = isl_union_map_coalesce (dependences);
331 : :
332 : 126 : if (dump_file)
333 : : {
334 : 61 : fprintf (dump_file, "data dependences (\n");
335 : 61 : print_isl_union_map (dump_file, dependences);
336 : 61 : fprintf (dump_file, ")\n");
337 : : }
338 : :
339 : 126 : scop->dependence = dependences;
340 : : }
341 : :
342 : : #endif /* HAVE_isl */
|
