Line data Source code
1 : /* Data dependence analysis for Graphite.
2 : Copyright (C) 2009-2026 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 1439 : constrain_domain (isl_map *map, isl_set *s)
46 : {
47 1439 : isl_space *d = isl_map_get_space (map);
48 1439 : isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
49 :
50 1439 : s = isl_set_set_tuple_id (s, id);
51 1439 : isl_space_free (d);
52 1439 : 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 1439 : add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
59 : {
60 1439 : isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
61 : isl_set_copy (pdr->subscript_sizes));
62 1439 : x = isl_map_coalesce (x);
63 1439 : 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 135 : 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 135 : int i, j;
75 135 : poly_bb_p pbb;
76 135 : poly_dr_p pdr;
77 :
78 977 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
79 : {
80 2281 : FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) {
81 1439 : if (pdr_read_p (pdr))
82 : {
83 654 : if (dump_file)
84 : {
85 337 : fprintf (dump_file, "Adding read to depedence graph: ");
86 337 : print_pdr (dump_file, pdr);
87 : }
88 654 : isl_union_map *um
89 654 : = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
90 654 : reads = isl_union_map_union (reads, um);
91 654 : if (dump_file)
92 : {
93 337 : fprintf (dump_file, "Reads depedence graph: ");
94 337 : print_isl_union_map (dump_file, reads);
95 : }
96 : }
97 785 : else if (pdr_write_p (pdr))
98 : {
99 785 : if (dump_file)
100 : {
101 415 : fprintf (dump_file, "Adding must write to depedence graph: ");
102 415 : print_pdr (dump_file, pdr);
103 : }
104 785 : isl_union_map *um
105 785 : = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
106 785 : must_writes = isl_union_map_union (must_writes, um);
107 785 : if (dump_file)
108 : {
109 415 : fprintf (dump_file, "Must writes depedence graph: ");
110 415 : 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 135 : }
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 135 : scop_get_dependences (scop_p scop)
261 : {
262 135 : if (scop->dependence)
263 0 : return;
264 :
265 135 : isl_space *space = isl_set_get_space (scop->param_context);
266 135 : isl_union_map *reads = isl_union_map_empty (isl_space_copy (space));
267 135 : isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space));
268 135 : isl_union_map *may_writes = isl_union_map_empty (space);
269 135 : scop_get_reads_and_writes (scop, reads, must_writes, may_writes);
270 :
271 135 : if (dump_file)
272 : {
273 62 : fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
274 62 : fprintf (dump_file, "Statements on the iteration domain are mapped to"
275 : " array references.\n");
276 62 : fprintf (dump_file, " To read the following data references:\n\n");
277 62 : fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
278 62 : fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
279 :
280 62 : 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 62 : fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1"
283 : " and first subscript access i0.\n");
284 62 : 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 62 : fprintf (dump_file, "-----------------------\n\n");
288 :
289 62 : fprintf (dump_file, "data references (\n");
290 62 : fprintf (dump_file, " reads: ");
291 62 : print_isl_union_map (dump_file, reads);
292 62 : fprintf (dump_file, " must_writes: ");
293 62 : print_isl_union_map (dump_file, must_writes);
294 62 : fprintf (dump_file, " may_writes: ");
295 62 : print_isl_union_map (dump_file, may_writes);
296 62 : fprintf (dump_file, ")\n");
297 : }
298 :
299 135 : gcc_assert (scop->original_schedule);
300 :
301 135 : isl_union_access_info *ai;
302 135 : ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
303 135 : ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
304 135 : ai = isl_union_access_info_set_may_source (ai, may_writes);
305 135 : ai = isl_union_access_info_set_schedule
306 135 : (ai, isl_schedule_copy (scop->original_schedule));
307 135 : isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
308 135 : isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
309 135 : isl_union_flow_free (flow);
310 :
311 135 : ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
312 135 : ai = isl_union_access_info_set_must_source (ai, must_writes);
313 135 : ai = isl_union_access_info_set_may_source (ai, reads);
314 135 : ai = isl_union_access_info_set_schedule
315 135 : (ai, isl_schedule_copy (scop->original_schedule));
316 135 : flow = isl_union_access_info_compute_flow (ai);
317 :
318 135 : isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
319 135 : isl_union_map *war = isl_union_flow_get_may_dependence (flow);
320 135 : war = isl_union_map_subtract (war, isl_union_map_copy (waw));
321 135 : isl_union_flow_free (flow);
322 :
323 135 : raw = isl_union_map_coalesce (raw);
324 135 : waw = isl_union_map_coalesce (waw);
325 135 : war = isl_union_map_coalesce (war);
326 :
327 135 : isl_union_map *dependences = raw;
328 135 : dependences = isl_union_map_union (dependences, war);
329 135 : dependences = isl_union_map_union (dependences, waw);
330 135 : dependences = isl_union_map_coalesce (dependences);
331 :
332 135 : if (dump_file)
333 : {
334 62 : fprintf (dump_file, "data dependences (\n");
335 62 : print_isl_union_map (dump_file, dependences);
336 62 : fprintf (dump_file, ")\n");
337 : }
338 :
339 135 : scop->dependence = dependences;
340 : }
341 :
342 : #endif /* HAVE_isl */
|
