Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-dependences.c @ 111:04ced10e8804

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