]>
Commit | Line | Data |
---|---|---|
c6bb733d | 1 | /* Data dependence analysis for Graphite. |
7cf0dbf3 | 2 | Copyright (C) 2009, 2010 Free Software Foundation, Inc. |
c6bb733d | 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 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
c6bb733d | 25 | #include "tree-flow.h" |
c6bb733d | 26 | #include "tree-dump.h" |
c6bb733d | 27 | #include "cfgloop.h" |
28 | #include "tree-chrec.h" | |
29 | #include "tree-data-ref.h" | |
30 | #include "tree-scalar-evolution.h" | |
1e5b7b1f | 31 | #include "sese.h" |
c6bb733d | 32 | |
33 | #ifdef HAVE_cloog | |
c6bb733d | 34 | #include "ppl_c.h" |
c6bb733d | 35 | #include "graphite-ppl.h" |
c6bb733d | 36 | #include "graphite-poly.h" |
37 | #include "graphite-dependences.h" | |
38 | ||
0d6b5db2 | 39 | /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is |
a071b80b | 40 | the source data reference, SINK is the sink data reference. When |
41 | the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE | |
42 | and SINK are in dependence as described by DDP. */ | |
0d6b5db2 | 43 | |
44 | static poly_ddr_p | |
45 | new_poly_ddr (poly_dr_p source, poly_dr_p sink, | |
a071b80b | 46 | ppl_Pointset_Powerset_C_Polyhedron_t ddp, |
47 | bool original_scattering_p) | |
c6bb733d | 48 | { |
a071b80b | 49 | poly_ddr_p pddr = XNEW (struct poly_ddr); |
0d6b5db2 | 50 | |
0d6b5db2 | 51 | PDDR_SOURCE (pddr) = source; |
52 | PDDR_SINK (pddr) = sink; | |
53 | PDDR_DDP (pddr) = ddp; | |
a071b80b | 54 | PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p; |
55 | ||
56 | if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp)) | |
57 | PDDR_KIND (pddr) = no_dependence; | |
58 | else | |
59 | PDDR_KIND (pddr) = has_dependence; | |
0d6b5db2 | 60 | |
61 | return pddr; | |
62 | } | |
c6bb733d | 63 | |
0d6b5db2 | 64 | /* Free the poly_ddr_p P. */ |
c6bb733d | 65 | |
0d6b5db2 | 66 | void |
67 | free_poly_ddr (void *p) | |
68 | { | |
69 | poly_ddr_p pddr = (poly_ddr_p) p; | |
70 | ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr)); | |
71 | free (pddr); | |
c6bb733d | 72 | } |
73 | ||
0d6b5db2 | 74 | /* Comparison function for poly_ddr hash table. */ |
c6bb733d | 75 | |
76 | int | |
0d6b5db2 | 77 | eq_poly_ddr_p (const void *pddr1, const void *pddr2) |
c6bb733d | 78 | { |
0d6b5db2 | 79 | const struct poly_ddr *p1 = (const struct poly_ddr *) pddr1; |
80 | const struct poly_ddr *p2 = (const struct poly_ddr *) pddr2; | |
c6bb733d | 81 | |
0d6b5db2 | 82 | return (PDDR_SOURCE (p1) == PDDR_SOURCE (p2) |
83 | && PDDR_SINK (p1) == PDDR_SINK (p2)); | |
c6bb733d | 84 | } |
85 | ||
0d6b5db2 | 86 | /* Hash function for poly_ddr hashtable. */ |
c6bb733d | 87 | |
88 | hashval_t | |
0d6b5db2 | 89 | hash_poly_ddr_p (const void *pddr) |
c6bb733d | 90 | { |
0d6b5db2 | 91 | const struct poly_ddr *p = (const struct poly_ddr *) pddr; |
92 | ||
93 | return (hashval_t) ((long) PDDR_SOURCE (p) + (long) PDDR_SINK (p)); | |
94 | } | |
95 | ||
96 | /* Returns true when PDDR has no dependence. */ | |
c6bb733d | 97 | |
0d6b5db2 | 98 | static bool |
99 | pddr_is_empty (poly_ddr_p pddr) | |
100 | { | |
a071b80b | 101 | if (!pddr) |
102 | return true; | |
103 | ||
104 | gcc_assert (PDDR_KIND (pddr) != unknown_dependence); | |
105 | ||
106 | return PDDR_KIND (pddr) == no_dependence ? true : false; | |
107 | } | |
108 | ||
109 | /* Prints to FILE the layout of the dependence polyhedron of PDDR: | |
110 | ||
111 | T1|I1|T2|I2|S1|S2|G | |
112 | ||
113 | with | |
114 | | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK | |
115 | | I1 and I2 the iteration domains | |
116 | | S1 and S2 the subscripts | |
117 | | G the global parameters. */ | |
118 | ||
119 | static void | |
120 | print_dependence_polyhedron_layout (FILE *file, poly_ddr_p pddr) | |
121 | { | |
122 | poly_dr_p pdr1 = PDDR_SOURCE (pddr); | |
123 | poly_dr_p pdr2 = PDDR_SINK (pddr); | |
124 | poly_bb_p pbb1 = PDR_PBB (pdr1); | |
125 | poly_bb_p pbb2 = PDR_PBB (pdr2); | |
126 | ||
127 | graphite_dim_t i; | |
128 | graphite_dim_t tdim1 = PDDR_ORIGINAL_SCATTERING_P (pddr) ? | |
129 | pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1); | |
130 | graphite_dim_t tdim2 = PDDR_ORIGINAL_SCATTERING_P (pddr) ? | |
131 | pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2); | |
132 | graphite_dim_t idim1 = pbb_dim_iter_domain (pbb1); | |
133 | graphite_dim_t idim2 = pbb_dim_iter_domain (pbb2); | |
134 | graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1; | |
135 | graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1; | |
136 | graphite_dim_t gdim = scop_nb_params (PBB_SCOP (pbb1)); | |
137 | ||
138 | fprintf (file, "# eq"); | |
139 | ||
140 | for (i = 0; i < tdim1; i++) | |
141 | fprintf (file, " t1_%d", (int) i); | |
142 | for (i = 0; i < idim1; i++) | |
143 | fprintf (file, " i1_%d", (int) i); | |
144 | for (i = 0; i < tdim2; i++) | |
145 | fprintf (file, " t2_%d", (int) i); | |
146 | for (i = 0; i < idim2; i++) | |
147 | fprintf (file, " i2_%d", (int) i); | |
148 | for (i = 0; i < sdim1; i++) | |
149 | fprintf (file, " s1_%d", (int) i); | |
150 | for (i = 0; i < sdim2; i++) | |
151 | fprintf (file, " s2_%d", (int) i); | |
152 | for (i = 0; i < gdim; i++) | |
153 | fprintf (file, " g_%d", (int) i); | |
154 | ||
155 | fprintf (file, " cst\n"); | |
156 | } | |
157 | ||
158 | /* Prints to FILE the poly_ddr_p PDDR. */ | |
159 | ||
160 | void | |
161 | print_pddr (FILE *file, poly_ddr_p pddr) | |
162 | { | |
163 | fprintf (file, "pddr (kind: "); | |
164 | ||
165 | if (PDDR_KIND (pddr) == unknown_dependence) | |
166 | fprintf (file, "unknown_dependence"); | |
167 | else if (PDDR_KIND (pddr) == no_dependence) | |
168 | fprintf (file, "no_dependence"); | |
169 | else if (PDDR_KIND (pddr) == has_dependence) | |
170 | fprintf (file, "has_dependence"); | |
171 | ||
172 | fprintf (file, "\n source "); | |
ff4c7a5a | 173 | print_pdr (file, PDDR_SOURCE (pddr), 2); |
0d6b5db2 | 174 | |
a071b80b | 175 | fprintf (file, "\n sink "); |
ff4c7a5a | 176 | print_pdr (file, PDDR_SINK (pddr), 2); |
a071b80b | 177 | |
178 | if (PDDR_KIND (pddr) == has_dependence) | |
0d6b5db2 | 179 | { |
a071b80b | 180 | fprintf (file, "\n dependence polyhedron (\n"); |
181 | print_dependence_polyhedron_layout (file, pddr); | |
182 | ppl_print_powerset_matrix (file, PDDR_DDP (pddr)); | |
183 | fprintf (file, ")\n"); | |
0d6b5db2 | 184 | } |
185 | ||
a071b80b | 186 | fprintf (file, ")\n"); |
187 | } | |
188 | ||
189 | /* Prints to STDERR the poly_ddr_p PDDR. */ | |
190 | ||
4b987fac | 191 | DEBUG_FUNCTION void |
a071b80b | 192 | debug_pddr (poly_ddr_p pddr) |
193 | { | |
194 | print_pddr (stderr, pddr); | |
195 | } | |
196 | ||
197 | ||
198 | /* Remove all the dimensions except alias information at dimension | |
199 | ALIAS_DIM. */ | |
200 | ||
201 | static void | |
202 | build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset, | |
203 | ppl_dimension_type alias_dim) | |
204 | { | |
205 | ppl_dimension_type *ds; | |
206 | ppl_dimension_type access_dim; | |
207 | unsigned i, pos = 0; | |
208 | ||
209 | ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset, | |
210 | &access_dim); | |
211 | ds = XNEWVEC (ppl_dimension_type, access_dim-1); | |
212 | for (i = 0; i < access_dim; i++) | |
213 | { | |
214 | if (i == alias_dim) | |
215 | continue; | |
216 | ||
217 | ds[pos] = i; | |
218 | pos++; | |
219 | } | |
220 | ||
221 | ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset, | |
222 | ds, | |
223 | access_dim - 1); | |
224 | free (ds); | |
225 | } | |
226 | ||
227 | /* Return true when PDR1 and PDR2 may alias. */ | |
228 | ||
229 | static bool | |
230 | poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2) | |
231 | { | |
232 | ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2; | |
233 | ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1); | |
234 | ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2); | |
235 | ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1); | |
236 | ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2); | |
237 | int empty_p; | |
238 | ||
239 | ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron | |
240 | (&alias_powerset1, accesses1); | |
241 | ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron | |
242 | (&alias_powerset2, accesses2); | |
243 | ||
244 | build_alias_set_powerset (alias_powerset1, alias_dim1); | |
245 | build_alias_set_powerset (alias_powerset2, alias_dim2); | |
246 | ||
247 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign | |
248 | (alias_powerset1, alias_powerset2); | |
249 | ||
250 | empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1); | |
251 | ||
252 | ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1); | |
253 | ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2); | |
254 | ||
255 | return !empty_p; | |
c6bb733d | 256 | } |
257 | ||
c6bb733d | 258 | /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is |
259 | transformed into "a CUT0 c CUT1' b" | |
260 | ||
261 | Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b" | |
262 | Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b" | |
263 | Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b": | |
264 | "00...0 a 00...0 c 00...0 b". */ | |
265 | ||
266 | static ppl_Pointset_Powerset_C_Polyhedron_t | |
267 | map_dr_into_dep_poly (graphite_dim_t dim, | |
268 | ppl_Pointset_Powerset_C_Polyhedron_t dr, | |
269 | graphite_dim_t cut0, graphite_dim_t cut1, | |
270 | graphite_dim_t nb0, graphite_dim_t nb1) | |
271 | { | |
272 | ppl_dimension_type pdim; | |
273 | ppl_dimension_type *map; | |
274 | ppl_Pointset_Powerset_C_Polyhedron_t res; | |
275 | ppl_dimension_type i; | |
276 | ||
277 | ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron | |
278 | (&res, dr); | |
279 | ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim); | |
280 | ||
281 | map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim); | |
282 | ||
283 | /* First mapping: move 'g' vector to right position. */ | |
284 | for (i = 0; i < cut0; i++) | |
285 | map[i] = i; | |
286 | ||
287 | for (i = cut0; i < cut1; i++) | |
288 | map[i] = pdim - cut1 + i; | |
289 | ||
290 | for (i = cut1; i < pdim; i++) | |
291 | map[i] = cut0 + i - cut1; | |
292 | ||
293 | ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim); | |
294 | free (map); | |
295 | ||
296 | /* After swapping 's' and 'g' vectors, we have to update a new cut. */ | |
297 | cut1 = pdim - cut1 + cut0; | |
298 | ||
299 | ppl_insert_dimensions_pointset (res, 0, nb0); | |
300 | ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1); | |
301 | ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1, | |
302 | dim - nb0 - nb1 - pdim); | |
303 | ||
304 | return res; | |
305 | } | |
306 | ||
c6bb733d | 307 | /* Builds subscript equality constraints. */ |
308 | ||
309 | static ppl_Pointset_Powerset_C_Polyhedron_t | |
310 | dr_equality_constraints (graphite_dim_t dim, | |
311 | graphite_dim_t pos, graphite_dim_t nb_subscripts) | |
312 | { | |
b57cb73e | 313 | ppl_Polyhedron_t eqs; |
c6bb733d | 314 | ppl_Pointset_Powerset_C_Polyhedron_t res; |
c6bb733d | 315 | graphite_dim_t i; |
316 | ||
b57cb73e | 317 | ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0); |
c6bb733d | 318 | |
c6bb733d | 319 | for (i = 0; i < nb_subscripts; i++) |
320 | { | |
b57cb73e | 321 | ppl_Constraint_t cstr |
322 | = ppl_build_relation (dim, pos + i, pos + i + nb_subscripts, | |
323 | 0, PPL_CONSTRAINT_TYPE_EQUAL); | |
324 | ppl_Polyhedron_add_constraint (eqs, cstr); | |
c6bb733d | 325 | ppl_delete_Constraint (cstr); |
c6bb733d | 326 | } |
327 | ||
b57cb73e | 328 | ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs); |
329 | ppl_delete_Polyhedron (eqs); | |
c6bb733d | 330 | return res; |
331 | } | |
332 | ||
abc97125 | 333 | /* Builds scheduling inequality constraints: when DIRECTION is |
334 | 1 builds a GE constraint, | |
335 | 0 builds an EQ constraint, | |
336 | -1 builds a LE constraint. */ | |
c6bb733d | 337 | |
338 | static ppl_Pointset_Powerset_C_Polyhedron_t | |
abc97125 | 339 | build_pairwise_scheduling (graphite_dim_t dim, |
340 | graphite_dim_t pos, | |
341 | graphite_dim_t offset, | |
342 | int direction) | |
c6bb733d | 343 | { |
344 | ppl_Pointset_Powerset_C_Polyhedron_t res; | |
345 | ppl_Polyhedron_t equalities; | |
346 | ppl_Constraint_t cstr; | |
347 | ||
348 | ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0); | |
349 | ||
abc97125 | 350 | switch (direction) |
351 | { | |
352 | case -1: | |
353 | cstr = ppl_build_relation (dim, pos, pos + offset, 1, | |
354 | PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); | |
355 | break; | |
c6bb733d | 356 | |
abc97125 | 357 | case 0: |
358 | cstr = ppl_build_relation (dim, pos, pos + offset, 0, | |
359 | PPL_CONSTRAINT_TYPE_EQUAL); | |
360 | break; | |
c6bb733d | 361 | |
abc97125 | 362 | case 1: |
363 | cstr = ppl_build_relation (dim, pos, pos + offset, -1, | |
364 | PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); | |
365 | break; | |
c6bb733d | 366 | |
abc97125 | 367 | default: |
368 | gcc_unreachable (); | |
369 | } | |
c6bb733d | 370 | |
371 | ppl_Polyhedron_add_constraint (equalities, cstr); | |
372 | ppl_delete_Constraint (cstr); | |
373 | ||
374 | ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities); | |
375 | ppl_delete_Polyhedron (equalities); | |
376 | return res; | |
377 | } | |
378 | ||
b7ac929d | 379 | /* Add to a non empty polyhedron BAG the precedence constraints for |
380 | the lexicographical comparison of time vectors in BAG following the | |
381 | lexicographical order. DIM is the dimension of the polyhedron BAG. | |
4fe30658 | 382 | TDIM is the number of loops common to the two statements that are |
383 | compared lexicographically, i.e. the number of loops containing | |
384 | both statements. OFFSET is the number of dimensions needed to | |
385 | represent the first statement, i.e. dimT1 + dimI1 in the layout of | |
b7ac929d | 386 | the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to |
f21ef1e7 | 387 | 1, compute the direct dependence from PDR1 to PDR2, and when |
388 | DIRECTION is -1, compute the reversed dependence relation, from | |
389 | PDR2 to PDR1. */ | |
c6bb733d | 390 | |
b7ac929d | 391 | static ppl_Pointset_Powerset_C_Polyhedron_t |
392 | build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag, | |
a071b80b | 393 | graphite_dim_t dim, |
394 | graphite_dim_t tdim, | |
395 | graphite_dim_t offset, | |
396 | int direction) | |
c6bb733d | 397 | { |
398 | graphite_dim_t i; | |
b7ac929d | 399 | ppl_Pointset_Powerset_C_Polyhedron_t res, lex; |
400 | ||
401 | ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1); | |
402 | ||
403 | lex = build_pairwise_scheduling (dim, 0, offset, direction); | |
404 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); | |
c6bb733d | 405 | |
b7ac929d | 406 | if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex)) |
407 | ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); | |
408 | ||
409 | ppl_delete_Pointset_Powerset_C_Polyhedron (lex); | |
410 | ||
411 | for (i = 0; i < tdim - 1; i++) | |
c6bb733d | 412 | { |
b7ac929d | 413 | ppl_Pointset_Powerset_C_Polyhedron_t sceq; |
414 | ||
415 | sceq = build_pairwise_scheduling (dim, i, offset, 0); | |
416 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq); | |
417 | ppl_delete_Pointset_Powerset_C_Polyhedron (sceq); | |
418 | ||
419 | lex = build_pairwise_scheduling (dim, i + 1, offset, direction); | |
420 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); | |
421 | ||
422 | if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex)) | |
423 | ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); | |
424 | ||
425 | ppl_delete_Pointset_Powerset_C_Polyhedron (lex); | |
c6bb733d | 426 | } |
a071b80b | 427 | |
b7ac929d | 428 | return res; |
c6bb733d | 429 | } |
430 | ||
bff9278d | 431 | /* Build the dependence polyhedron for data references PDR1 and PDR2. |
432 | The layout of the dependence polyhedron is: | |
433 | ||
434 | T1|I1|T2|I2|S1|S2|G | |
435 | ||
436 | with | |
437 | | T1 and T2 the scattering dimensions for PDR1 and PDR2 | |
438 | | I1 and I2 the iteration domains | |
439 | | S1 and S2 the subscripts | |
4fe30658 | 440 | | G the global parameters. |
441 | ||
f21ef1e7 | 442 | When DIRECTION is set to 1, compute the direct dependence from PDR1 |
443 | to PDR2, and when DIRECTION is -1, compute the reversed dependence | |
444 | relation, from PDR2 to PDR1. */ | |
c6bb733d | 445 | |
a071b80b | 446 | static ppl_Pointset_Powerset_C_Polyhedron_t |
447 | dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2, | |
448 | int direction, bool original_scattering_p) | |
c6bb733d | 449 | { |
a071b80b | 450 | poly_bb_p pbb1 = PDR_PBB (pdr1); |
451 | poly_bb_p pbb2 = PDR_PBB (pdr2); | |
c6bb733d | 452 | scop_p scop = PBB_SCOP (pbb1); |
453 | graphite_dim_t tdim1 = original_scattering_p ? | |
454 | pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1); | |
455 | graphite_dim_t tdim2 = original_scattering_p ? | |
456 | pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2); | |
457 | graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1); | |
458 | graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2); | |
85f74b79 | 459 | graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1; |
5f2e51eb | 460 | graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1; |
c6bb733d | 461 | graphite_dim_t gdim = scop_nb_params (scop); |
462 | graphite_dim_t dim1 = pdr_dim (pdr1); | |
463 | graphite_dim_t dim2 = pdr_dim (pdr2); | |
38e3217b | 464 | graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim; |
c6bb733d | 465 | ppl_Pointset_Powerset_C_Polyhedron_t res; |
5f2e51eb | 466 | ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2; |
c6bb733d | 467 | ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq; |
468 | ||
469 | gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2)); | |
bff9278d | 470 | |
5f2e51eb | 471 | combine_context_id_scat (&sc1, pbb1, original_scattering_p); |
472 | combine_context_id_scat (&sc2, pbb2, original_scattering_p); | |
bff9278d | 473 | |
5f2e51eb | 474 | ppl_insert_dimensions_pointset (sc1, tdim1 + ddim1, |
475 | tdim2 + ddim2 + sdim1 + sdim2); | |
c6bb733d | 476 | |
5f2e51eb | 477 | ppl_insert_dimensions_pointset (sc2, 0, tdim1 + ddim1); |
478 | ppl_insert_dimensions_pointset (sc2, tdim1 + ddim1 + tdim2 + ddim2, | |
479 | sdim1 + sdim2); | |
c6bb733d | 480 | |
481 | idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim, | |
482 | tdim1, tdim2 + ddim2); | |
483 | idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim, | |
484 | tdim1 + ddim1 + tdim2, sdim1); | |
485 | ||
486 | /* Now add the subscript equalities. */ | |
487 | dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1); | |
488 | ||
489 | ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0); | |
5f2e51eb | 490 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc1); |
491 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc2); | |
c6bb733d | 492 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1); |
493 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2); | |
494 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq); | |
c6bb733d | 495 | ppl_delete_Pointset_Powerset_C_Polyhedron (sc1); |
496 | ppl_delete_Pointset_Powerset_C_Polyhedron (sc2); | |
c6bb733d | 497 | ppl_delete_Pointset_Powerset_C_Polyhedron (idr1); |
498 | ppl_delete_Pointset_Powerset_C_Polyhedron (idr2); | |
499 | ppl_delete_Pointset_Powerset_C_Polyhedron (dreq); | |
500 | ||
501 | if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res)) | |
b7ac929d | 502 | { |
503 | ppl_Pointset_Powerset_C_Polyhedron_t lex = | |
504 | build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2), | |
505 | tdim1 + ddim1, direction); | |
506 | ppl_delete_Pointset_Powerset_C_Polyhedron (res); | |
507 | res = lex; | |
508 | } | |
0d6b5db2 | 509 | |
a071b80b | 510 | return res; |
c6bb733d | 511 | } |
512 | ||
513 | /* Build the dependence polyhedron for data references PDR1 and PDR2. | |
4fe30658 | 514 | If possible use already cached information. |
515 | ||
f21ef1e7 | 516 | When DIRECTION is set to 1, compute the direct dependence from PDR1 |
517 | to PDR2, and when DIRECTION is -1, compute the reversed dependence | |
518 | relation, from PDR2 to PDR1. */ | |
c6bb733d | 519 | |
0d6b5db2 | 520 | static poly_ddr_p |
a071b80b | 521 | dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2, |
522 | int direction, bool original_scattering_p) | |
c6bb733d | 523 | { |
c6bb733d | 524 | PTR *x = NULL; |
0d6b5db2 | 525 | poly_ddr_p res; |
a071b80b | 526 | ppl_Pointset_Powerset_C_Polyhedron_t ddp; |
c6bb733d | 527 | |
a071b80b | 528 | /* Return the PDDR from the cache if it already has been computed. */ |
c6bb733d | 529 | if (original_scattering_p) |
530 | { | |
0d6b5db2 | 531 | struct poly_ddr tmp; |
a071b80b | 532 | scop_p scop = PBB_SCOP (PDR_PBB (pdr1)); |
0d6b5db2 | 533 | |
c6bb733d | 534 | tmp.source = pdr1; |
535 | tmp.sink = pdr2; | |
a071b80b | 536 | x = htab_find_slot (SCOP_ORIGINAL_PDDRS (scop), |
c6bb733d | 537 | &tmp, INSERT); |
538 | ||
539 | if (x && *x) | |
0d6b5db2 | 540 | return (poly_ddr_p) *x; |
c6bb733d | 541 | } |
542 | ||
a071b80b | 543 | if ((pdr_read_p (pdr1) && pdr_read_p (pdr2)) |
544 | || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) | |
545 | || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2) | |
546 | || !poly_drs_may_alias_p (pdr1, pdr2)) | |
547 | ddp = NULL; | |
548 | else | |
549 | ddp = dependence_polyhedron_1 (pdr1, pdr2, direction, | |
550 | original_scattering_p); | |
551 | ||
552 | res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p); | |
c6bb733d | 553 | |
8fe76250 | 554 | if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) |
555 | && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) | |
556 | && poly_drs_may_alias_p (pdr1, pdr2)) | |
557 | PDDR_KIND (res) = unknown_dependence; | |
558 | ||
c6bb733d | 559 | if (original_scattering_p) |
0d6b5db2 | 560 | *x = res; |
c6bb733d | 561 | |
562 | return res; | |
563 | } | |
564 | ||
f007fe97 | 565 | /* Return true when the data dependence relation between the data |
566 | references PDR1 belonging to PBB1 and PDR2 is part of a | |
567 | reduction. */ | |
568 | ||
569 | static inline bool | |
570 | reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2) | |
571 | { | |
572 | int i; | |
573 | poly_dr_p pdr; | |
574 | ||
48148244 | 575 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr) |
f007fe97 | 576 | if (PDR_TYPE (pdr) == PDR_WRITE) |
577 | break; | |
578 | ||
579 | return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2); | |
580 | } | |
581 | ||
582 | /* Return true when the data dependence relation between the data | |
583 | references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is | |
584 | part of a reduction. */ | |
585 | ||
586 | static inline bool | |
a071b80b | 587 | reduction_dr_p (poly_dr_p pdr1, poly_dr_p pdr2) |
f007fe97 | 588 | { |
a071b80b | 589 | poly_bb_p pbb1 = PDR_PBB (pdr1); |
590 | poly_bb_p pbb2 = PDR_PBB (pdr2); | |
591 | ||
f007fe97 | 592 | if (PBB_IS_REDUCTION (pbb1)) |
593 | return reduction_dr_1 (pbb1, pdr1, pdr2); | |
594 | ||
595 | if (PBB_IS_REDUCTION (pbb2)) | |
596 | return reduction_dr_1 (pbb2, pdr2, pdr1); | |
597 | ||
598 | return false; | |
599 | } | |
600 | ||
c6bb733d | 601 | /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1 |
602 | and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING | |
603 | functions. */ | |
604 | ||
605 | static bool | |
a071b80b | 606 | graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2) |
c6bb733d | 607 | { |
0d6b5db2 | 608 | ppl_Pointset_Powerset_C_Polyhedron_t po, pt; |
70a1a7a2 | 609 | graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2; |
a071b80b | 610 | ppl_Pointset_Powerset_C_Polyhedron_t po_temp; |
70a1a7a2 | 611 | ppl_dimension_type pdim; |
612 | bool is_empty_p; | |
a071b80b | 613 | poly_ddr_p opddr, tpddr; |
614 | poly_bb_p pbb1, pbb2; | |
c6bb733d | 615 | |
a071b80b | 616 | if (reduction_dr_p (pdr1, pdr2)) |
f007fe97 | 617 | return true; |
618 | ||
a071b80b | 619 | /* We build the reverse dependence relation for the transformed |
620 | scattering, such that when we intersect it with the original PO, | |
621 | we get an empty intersection when the transform is legal: | |
622 | i.e. the transform should reverse no dependences, and so PT, the | |
623 | reversed transformed PDDR, should have no constraint from PO. */ | |
624 | opddr = dependence_polyhedron (pdr1, pdr2, 1, true); | |
8fe76250 | 625 | |
626 | if (PDDR_KIND (opddr) == unknown_dependence) | |
627 | return false; | |
a071b80b | 628 | |
f21ef1e7 | 629 | /* There are no dependences between PDR1 and PDR2 in the original |
a071b80b | 630 | version of the program, or after the transform, so the |
631 | transform is legal. */ | |
632 | if (pddr_is_empty (opddr)) | |
c6bb733d | 633 | return true; |
c6bb733d | 634 | |
8fe76250 | 635 | tpddr = dependence_polyhedron (pdr1, pdr2, -1, false); |
636 | ||
637 | if (PDDR_KIND (tpddr) == unknown_dependence) | |
638 | { | |
639 | free_poly_ddr (tpddr); | |
640 | return false; | |
641 | } | |
642 | ||
a071b80b | 643 | if (pddr_is_empty (tpddr)) |
644 | { | |
645 | free_poly_ddr (tpddr); | |
646 | return true; | |
647 | } | |
0d6b5db2 | 648 | |
a071b80b | 649 | po = PDDR_DDP (opddr); |
650 | pt = PDDR_DDP (tpddr); | |
651 | ||
652 | /* Copy PO into PO_TEMP, such that PO is not destroyed. PO is | |
653 | stored in a cache and should not be modified or freed. */ | |
654 | ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim); | |
655 | ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp, | |
656 | pdim, 0); | |
657 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, po); | |
70a1a7a2 | 658 | |
a071b80b | 659 | /* Extend PO and PT to have the same dimensions. */ |
660 | pbb1 = PDR_PBB (pdr1); | |
661 | pbb2 = PDR_PBB (pdr2); | |
70a1a7a2 | 662 | ddim1 = pbb_dim_iter_domain (pbb1); |
663 | otdim1 = pbb_nb_scattering_orig (pbb1); | |
664 | otdim2 = pbb_nb_scattering_orig (pbb2); | |
665 | ttdim1 = pbb_nb_scattering_transform (pbb1); | |
666 | ttdim2 = pbb_nb_scattering_transform (pbb2); | |
a071b80b | 667 | ppl_insert_dimensions_pointset (po_temp, otdim1, ttdim1); |
668 | ppl_insert_dimensions_pointset (po_temp, otdim1 + ttdim1 + ddim1 + otdim2, | |
669 | ttdim2); | |
70a1a7a2 | 670 | ppl_insert_dimensions_pointset (pt, 0, otdim1); |
671 | ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2); | |
672 | ||
a071b80b | 673 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt); |
674 | is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp); | |
70a1a7a2 | 675 | |
a071b80b | 676 | ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp); |
677 | free_poly_ddr (tpddr); | |
678 | ||
679 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
680 | fprintf (dump_file, "\nloop carries dependency.\n"); | |
0d6b5db2 | 681 | |
70a1a7a2 | 682 | return is_empty_p; |
c6bb733d | 683 | } |
684 | ||
30f4f4a6 | 685 | /* Return true when the data dependence relation for PBB1 and PBB2 is |
686 | part of a reduction. */ | |
687 | ||
688 | static inline bool | |
f007fe97 | 689 | reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2) |
30f4f4a6 | 690 | { |
691 | return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1); | |
692 | } | |
693 | ||
c6bb733d | 694 | /* Iterates over the data references of PBB1 and PBB2 and detect |
695 | whether the transformed schedule is correct. */ | |
696 | ||
697 | static bool | |
698 | graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2) | |
699 | { | |
700 | int i, j; | |
701 | poly_dr_p pdr1, pdr2; | |
702 | ||
9e3531b5 | 703 | if (!PBB_PDR_DUPLICATES_REMOVED (pbb1)) |
704 | pbb_remove_duplicate_pdrs (pbb1); | |
705 | ||
706 | if (!PBB_PDR_DUPLICATES_REMOVED (pbb2)) | |
707 | pbb_remove_duplicate_pdrs (pbb2); | |
708 | ||
f007fe97 | 709 | if (reduction_ddr_p (pbb1, pbb2)) |
30f4f4a6 | 710 | return true; |
711 | ||
48148244 | 712 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) |
713 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) | |
a071b80b | 714 | if (!graphite_legal_transform_dr (pdr1, pdr2)) |
2b3a572c | 715 | return false; |
70a1a7a2 | 716 | |
c6bb733d | 717 | return true; |
718 | } | |
719 | ||
720 | /* Iterates over the SCOP and detect whether the transformed schedule | |
721 | is correct. */ | |
722 | ||
723 | bool | |
724 | graphite_legal_transform (scop_p scop) | |
725 | { | |
726 | int i, j; | |
727 | poly_bb_p pbb1, pbb2; | |
728 | ||
525c22c4 | 729 | timevar_push (TV_GRAPHITE_DATA_DEPS); |
730 | ||
48148244 | 731 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
732 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) | |
c6bb733d | 733 | if (!graphite_legal_transform_bb (pbb1, pbb2)) |
525c22c4 | 734 | { |
735 | timevar_pop (TV_GRAPHITE_DATA_DEPS); | |
736 | return false; | |
737 | } | |
c6bb733d | 738 | |
525c22c4 | 739 | timevar_pop (TV_GRAPHITE_DATA_DEPS); |
c6bb733d | 740 | return true; |
741 | } | |
742 | ||
c6bb733d | 743 | /* Returns TRUE when the dependence polyhedron between PDR1 and |
0d6b5db2 | 744 | PDR2 represents a loop carried dependence at level LEVEL. */ |
c6bb733d | 745 | |
746 | static bool | |
747 | graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2, | |
748 | int level) | |
749 | { | |
c6bb733d | 750 | ppl_Pointset_Powerset_C_Polyhedron_t po; |
751 | ppl_Pointset_Powerset_C_Polyhedron_t eqpp; | |
a071b80b | 752 | graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1)); |
753 | graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1)); | |
c6bb733d | 754 | ppl_dimension_type dim; |
755 | bool empty_p; | |
a071b80b | 756 | poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); |
0d6b5db2 | 757 | |
8fe76250 | 758 | if (PDDR_KIND (pddr) == unknown_dependence) |
759 | { | |
760 | free_poly_ddr (pddr); | |
761 | return true; | |
762 | } | |
763 | ||
0d6b5db2 | 764 | if (pddr_is_empty (pddr)) |
a071b80b | 765 | { |
766 | free_poly_ddr (pddr); | |
767 | return false; | |
768 | } | |
c6bb733d | 769 | |
0d6b5db2 | 770 | po = PDDR_DDP (pddr); |
c6bb733d | 771 | ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim); |
abc97125 | 772 | eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1); |
c6bb733d | 773 | |
774 | ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po); | |
775 | empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp); | |
776 | ||
c6bb733d | 777 | ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp); |
a071b80b | 778 | free_poly_ddr (pddr); |
779 | ||
c6bb733d | 780 | return !empty_p; |
781 | } | |
782 | ||
783 | /* Check data dependency between PBB1 and PBB2 at level LEVEL. */ | |
784 | ||
785 | bool | |
786 | dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level) | |
787 | { | |
788 | int i, j; | |
789 | poly_dr_p pdr1, pdr2; | |
790 | ||
525c22c4 | 791 | timevar_push (TV_GRAPHITE_DATA_DEPS); |
792 | ||
48148244 | 793 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) |
794 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) | |
c6bb733d | 795 | if (graphite_carried_dependence_level_k (pdr1, pdr2, level)) |
525c22c4 | 796 | { |
797 | timevar_pop (TV_GRAPHITE_DATA_DEPS); | |
798 | return true; | |
799 | } | |
c6bb733d | 800 | |
525c22c4 | 801 | timevar_pop (TV_GRAPHITE_DATA_DEPS); |
c6bb733d | 802 | return false; |
803 | } | |
804 | ||
de38f9c0 | 805 | /* Pretty print to FILE all the original data dependences of SCoP in |
806 | DOT format. */ | |
a7d089ac | 807 | |
808 | static void | |
de38f9c0 | 809 | dot_original_deps_stmt_1 (FILE *file, scop_p scop) |
a7d089ac | 810 | { |
811 | int i, j, k, l; | |
812 | poly_bb_p pbb1, pbb2; | |
813 | poly_dr_p pdr1, pdr2; | |
814 | ||
48148244 | 815 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
816 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) | |
a7d089ac | 817 | { |
48148244 | 818 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) |
819 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) | |
a071b80b | 820 | if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true))) |
a7d089ac | 821 | { |
de38f9c0 | 822 | fprintf (file, "OS%d -> OS%d\n", |
a7d089ac | 823 | pbb_index (pbb1), pbb_index (pbb2)); |
824 | goto done; | |
825 | } | |
826 | done:; | |
827 | } | |
de38f9c0 | 828 | } |
a7d089ac | 829 | |
de38f9c0 | 830 | /* Pretty print to FILE all the transformed data dependences of SCoP in |
831 | DOT format. */ | |
832 | ||
833 | static void | |
834 | dot_transformed_deps_stmt_1 (FILE *file, scop_p scop) | |
835 | { | |
836 | int i, j, k, l; | |
837 | poly_bb_p pbb1, pbb2; | |
838 | poly_dr_p pdr1, pdr2; | |
839 | ||
48148244 | 840 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
841 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) | |
de38f9c0 | 842 | { |
48148244 | 843 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) |
844 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) | |
a071b80b | 845 | { |
846 | poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); | |
847 | ||
848 | if (!pddr_is_empty (pddr)) | |
849 | { | |
850 | fprintf (file, "TS%d -> TS%d\n", | |
851 | pbb_index (pbb1), pbb_index (pbb2)); | |
852 | ||
853 | free_poly_ddr (pddr); | |
854 | goto done; | |
855 | } | |
856 | ||
857 | free_poly_ddr (pddr); | |
858 | } | |
de38f9c0 | 859 | done:; |
860 | } | |
a7d089ac | 861 | } |
862 | ||
de38f9c0 | 863 | |
96b6d5d7 | 864 | /* Pretty print to FILE all the data dependences of SCoP in DOT |
865 | format. */ | |
866 | ||
867 | static void | |
de38f9c0 | 868 | dot_deps_stmt_1 (FILE *file, scop_p scop) |
869 | { | |
870 | fputs ("digraph all {\n", file); | |
871 | ||
872 | dot_original_deps_stmt_1 (file, scop); | |
873 | dot_transformed_deps_stmt_1 (file, scop); | |
874 | ||
875 | fputs ("}\n\n", file); | |
876 | } | |
877 | ||
878 | /* Pretty print to FILE all the original data dependences of SCoP in | |
879 | DOT format. */ | |
880 | ||
881 | static void | |
882 | dot_original_deps (FILE *file, scop_p scop) | |
96b6d5d7 | 883 | { |
884 | int i, j, k, l; | |
885 | poly_bb_p pbb1, pbb2; | |
886 | poly_dr_p pdr1, pdr2; | |
887 | ||
48148244 | 888 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
889 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) | |
890 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) | |
891 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) | |
a071b80b | 892 | if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true))) |
de38f9c0 | 893 | fprintf (file, "OS%d_D%d -> OS%d_D%d\n", |
96b6d5d7 | 894 | pbb_index (pbb1), PDR_ID (pdr1), |
895 | pbb_index (pbb2), PDR_ID (pdr2)); | |
de38f9c0 | 896 | } |
897 | ||
898 | /* Pretty print to FILE all the transformed data dependences of SCoP in | |
899 | DOT format. */ | |
900 | ||
901 | static void | |
902 | dot_transformed_deps (FILE *file, scop_p scop) | |
903 | { | |
904 | int i, j, k, l; | |
905 | poly_bb_p pbb1, pbb2; | |
906 | poly_dr_p pdr1, pdr2; | |
907 | ||
48148244 | 908 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
909 | FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) | |
910 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) | |
911 | FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) | |
a071b80b | 912 | { |
913 | poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); | |
914 | ||
915 | if (!pddr_is_empty (pddr)) | |
4f19d858 | 916 | fprintf (file, "TS%d_D%d -> TS%d_D%d\n", |
917 | pbb_index (pbb1), PDR_ID (pdr1), | |
918 | pbb_index (pbb2), PDR_ID (pdr2)); | |
a071b80b | 919 | |
920 | free_poly_ddr (pddr); | |
921 | } | |
de38f9c0 | 922 | } |
923 | ||
924 | /* Pretty print to FILE all the data dependences of SCoP in DOT | |
925 | format. */ | |
926 | ||
927 | static void | |
928 | dot_deps_1 (FILE *file, scop_p scop) | |
929 | { | |
930 | fputs ("digraph all {\n", file); | |
931 | ||
932 | dot_original_deps (file, scop); | |
933 | dot_transformed_deps (file, scop); | |
96b6d5d7 | 934 | |
935 | fputs ("}\n\n", file); | |
936 | } | |
937 | ||
938 | /* Display all the data dependences in SCoP using dotty. */ | |
939 | ||
6b5822fe | 940 | DEBUG_FUNCTION void |
96b6d5d7 | 941 | dot_deps (scop_p scop) |
942 | { | |
943 | /* When debugging, enable the following code. This cannot be used | |
944 | in production compilers because it calls "system". */ | |
c04f2da7 | 945 | #if 0 |
96b6d5d7 | 946 | FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); |
947 | gcc_assert (stream); | |
948 | ||
949 | dot_deps_1 (stream, scop); | |
950 | fclose (stream); | |
951 | ||
97b0e4df | 952 | system ("dotty /tmp/scopdeps.dot &"); |
96b6d5d7 | 953 | #else |
954 | dot_deps_1 (stderr, scop); | |
955 | #endif | |
956 | } | |
957 | ||
a7d089ac | 958 | /* Display all the statement dependences in SCoP using dotty. */ |
959 | ||
6b5822fe | 960 | DEBUG_FUNCTION void |
a7d089ac | 961 | dot_deps_stmt (scop_p scop) |
962 | { | |
963 | /* When debugging, enable the following code. This cannot be used | |
964 | in production compilers because it calls "system". */ | |
965 | #if 0 | |
a7d089ac | 966 | FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); |
967 | gcc_assert (stream); | |
968 | ||
969 | dot_deps_stmt_1 (stream, scop); | |
970 | fclose (stream); | |
971 | ||
97b0e4df | 972 | system ("dotty /tmp/scopdeps.dot &"); |
a7d089ac | 973 | #else |
4938b827 | 974 | dot_deps_stmt_1 (stderr, scop); |
a7d089ac | 975 | #endif |
976 | } | |
96b6d5d7 | 977 | |
c6bb733d | 978 | #endif |