Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-dependences.c @ 63:b7f97abdc517 gcc-4.6-20100522

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc from gcc-4.5.0 to gcc-4.6
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Mon, 24 May 2010 12:47:05 +0900
parents 77e2b8dfacca
children f6334be47118
comparison
equal deleted inserted replaced
56:3c8a44c06a95 63:b7f97abdc517
1 /* Data dependence analysis for Graphite. 1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009 Free Software Foundation, Inc. 2 Copyright (C) 2009, 2010 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
49 #include "graphite.h" 49 #include "graphite.h"
50 #include "graphite-poly.h" 50 #include "graphite-poly.h"
51 #include "graphite-dependences.h" 51 #include "graphite-dependences.h"
52 52
53 /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is 53 /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is
54 the source data reference, SINK is the sink data reference. SOURCE 54 the source data reference, SINK is the sink data reference. When
55 and SINK define an edge in the Data Dependence Graph (DDG). */ 55 the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE
56 and SINK are in dependence as described by DDP. */
56 57
57 static poly_ddr_p 58 static poly_ddr_p
58 new_poly_ddr (poly_dr_p source, poly_dr_p sink, 59 new_poly_ddr (poly_dr_p source, poly_dr_p sink,
59 ppl_Pointset_Powerset_C_Polyhedron_t ddp) 60 ppl_Pointset_Powerset_C_Polyhedron_t ddp,
60 { 61 bool original_scattering_p)
61 poly_ddr_p pddr; 62 {
62 63 poly_ddr_p pddr = XNEW (struct poly_ddr);
63 pddr = XNEW (struct poly_ddr); 64
64 PDDR_SOURCE (pddr) = source; 65 PDDR_SOURCE (pddr) = source;
65 PDDR_SINK (pddr) = sink; 66 PDDR_SINK (pddr) = sink;
66 PDDR_DDP (pddr) = ddp; 67 PDDR_DDP (pddr) = ddp;
67 PDDR_KIND (pddr) = unknown_dependence; 68 PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
69
70 if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
71 PDDR_KIND (pddr) = no_dependence;
72 else
73 PDDR_KIND (pddr) = has_dependence;
68 74
69 return pddr; 75 return pddr;
70 } 76 }
71 77
72 /* Free the poly_ddr_p P. */ 78 /* Free the poly_ddr_p P. */
104 /* Returns true when PDDR has no dependence. */ 110 /* Returns true when PDDR has no dependence. */
105 111
106 static bool 112 static bool
107 pddr_is_empty (poly_ddr_p pddr) 113 pddr_is_empty (poly_ddr_p pddr)
108 { 114 {
109 if (PDDR_KIND (pddr) != unknown_dependence) 115 if (!pddr)
110 return PDDR_KIND (pddr) == no_dependence ? true : false; 116 return true;
111 117
112 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PDDR_DDP (pddr))) 118 gcc_assert (PDDR_KIND (pddr) != unknown_dependence);
113 { 119
114 PDDR_KIND (pddr) = no_dependence; 120 return PDDR_KIND (pddr) == no_dependence ? true : false;
115 return true; 121 }
116 } 122
117 123 /* Prints to FILE the layout of the dependence polyhedron of PDDR:
118 PDDR_KIND (pddr) = has_dependence; 124
119 return false; 125 T1|I1|T2|I2|S1|S2|G
120 } 126
121 127 with
122 /* Returns a polyhedron of dimension DIM. 128 | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK
123 129 | I1 and I2 the iteration domains
124 Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET 130 | S1 and S2 the subscripts
125 and the dimensions [cut, ..., nb_dim] to DIM - GDIM. */ 131 | G the global parameters. */
126 132
127 static ppl_Pointset_Powerset_C_Polyhedron_t 133 static void
128 map_into_dep_poly (graphite_dim_t dim, graphite_dim_t gdim, 134 print_dependence_polyhedron_layout (FILE *file, poly_ddr_p pddr)
129 ppl_Pointset_Powerset_C_Polyhedron_t p, 135 {
130 graphite_dim_t cut, 136 poly_dr_p pdr1 = PDDR_SOURCE (pddr);
131 graphite_dim_t offset) 137 poly_dr_p pdr2 = PDDR_SINK (pddr);
132 { 138 poly_bb_p pbb1 = PDR_PBB (pdr1);
133 ppl_Pointset_Powerset_C_Polyhedron_t res; 139 poly_bb_p pbb2 = PDR_PBB (pdr2);
140
141 graphite_dim_t i;
142 graphite_dim_t tdim1 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
143 pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
144 graphite_dim_t tdim2 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
145 pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
146 graphite_dim_t idim1 = pbb_dim_iter_domain (pbb1);
147 graphite_dim_t idim2 = pbb_dim_iter_domain (pbb2);
148 graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
149 graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
150 graphite_dim_t gdim = scop_nb_params (PBB_SCOP (pbb1));
151
152 fprintf (file, "# eq");
153
154 for (i = 0; i < tdim1; i++)
155 fprintf (file, " t1_%d", (int) i);
156 for (i = 0; i < idim1; i++)
157 fprintf (file, " i1_%d", (int) i);
158 for (i = 0; i < tdim2; i++)
159 fprintf (file, " t2_%d", (int) i);
160 for (i = 0; i < idim2; i++)
161 fprintf (file, " i2_%d", (int) i);
162 for (i = 0; i < sdim1; i++)
163 fprintf (file, " s1_%d", (int) i);
164 for (i = 0; i < sdim2; i++)
165 fprintf (file, " s2_%d", (int) i);
166 for (i = 0; i < gdim; i++)
167 fprintf (file, " g_%d", (int) i);
168
169 fprintf (file, " cst\n");
170 }
171
172 /* Prints to FILE the poly_ddr_p PDDR. */
173
174 void
175 print_pddr (FILE *file, poly_ddr_p pddr)
176 {
177 fprintf (file, "pddr (kind: ");
178
179 if (PDDR_KIND (pddr) == unknown_dependence)
180 fprintf (file, "unknown_dependence");
181 else if (PDDR_KIND (pddr) == no_dependence)
182 fprintf (file, "no_dependence");
183 else if (PDDR_KIND (pddr) == has_dependence)
184 fprintf (file, "has_dependence");
185
186 fprintf (file, "\n source ");
187 print_pdr (file, PDDR_SOURCE (pddr), 2);
188
189 fprintf (file, "\n sink ");
190 print_pdr (file, PDDR_SINK (pddr), 2);
191
192 if (PDDR_KIND (pddr) == has_dependence)
193 {
194 fprintf (file, "\n dependence polyhedron (\n");
195 print_dependence_polyhedron_layout (file, pddr);
196 ppl_print_powerset_matrix (file, PDDR_DDP (pddr));
197 fprintf (file, ")\n");
198 }
199
200 fprintf (file, ")\n");
201 }
202
203 /* Prints to STDERR the poly_ddr_p PDDR. */
204
205 void
206 debug_pddr (poly_ddr_p pddr)
207 {
208 print_pddr (stderr, pddr);
209 }
210
211
212 /* Remove all the dimensions except alias information at dimension
213 ALIAS_DIM. */
214
215 static void
216 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
217 ppl_dimension_type alias_dim)
218 {
219 ppl_dimension_type *ds;
220 ppl_dimension_type access_dim;
221 unsigned i, pos = 0;
222
223 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
224 &access_dim);
225 ds = XNEWVEC (ppl_dimension_type, access_dim-1);
226 for (i = 0; i < access_dim; i++)
227 {
228 if (i == alias_dim)
229 continue;
230
231 ds[pos] = i;
232 pos++;
233 }
234
235 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
236 ds,
237 access_dim - 1);
238 free (ds);
239 }
240
241 /* Return true when PDR1 and PDR2 may alias. */
242
243 static bool
244 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
245 {
246 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
247 ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
248 ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
249 ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
250 ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
251 int empty_p;
134 252
135 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 253 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
136 (&res, p); 254 (&alias_powerset1, accesses1);
137 ppl_insert_dimensions_pointset (res, 0, offset); 255 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
138 ppl_insert_dimensions_pointset (res, offset + cut, 256 (&alias_powerset2, accesses2);
139 dim - offset - cut - gdim); 257
140 258 build_alias_set_powerset (alias_powerset1, alias_dim1);
141 return res; 259 build_alias_set_powerset (alias_powerset2, alias_dim2);
260
261 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
262 (alias_powerset1, alias_powerset2);
263
264 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
265
266 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
267 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
268
269 return !empty_p;
142 } 270 }
143 271
144 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is 272 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
145 transformed into "a CUT0 c CUT1' b" 273 transformed into "a CUT0 c CUT1' b"
146 274
188 dim - nb0 - nb1 - pdim); 316 dim - nb0 - nb1 - pdim);
189 317
190 return res; 318 return res;
191 } 319 }
192 320
193 /* Builds a constraints of the form "POS1 - POS2 CSTR_TYPE C" */
194
195 static ppl_Constraint_t
196 build_pairwise_constraint (graphite_dim_t dim,
197 graphite_dim_t pos1, graphite_dim_t pos2,
198 int c, enum ppl_enum_Constraint_Type cstr_type)
199 {
200 ppl_Linear_Expression_t expr;
201 ppl_Constraint_t cstr;
202 ppl_Coefficient_t coef;
203 Value v, v_op, v_c;
204
205 value_init (v);
206 value_init (v_op);
207 value_init (v_c);
208
209 value_set_si (v, 1);
210 value_set_si (v_op, -1);
211 value_set_si (v_c, c);
212
213 ppl_new_Coefficient (&coef);
214 ppl_new_Linear_Expression_with_dimension (&expr, dim);
215
216 ppl_assign_Coefficient_from_mpz_t (coef, v);
217 ppl_Linear_Expression_add_to_coefficient (expr, pos1, coef);
218 ppl_assign_Coefficient_from_mpz_t (coef, v_op);
219 ppl_Linear_Expression_add_to_coefficient (expr, pos2, coef);
220 ppl_assign_Coefficient_from_mpz_t (coef, v_c);
221 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
222
223 ppl_new_Constraint (&cstr, expr, cstr_type);
224
225 ppl_delete_Linear_Expression (expr);
226 ppl_delete_Coefficient (coef);
227 value_clear (v);
228 value_clear (v_op);
229 value_clear (v_c);
230
231 return cstr;
232 }
233
234 /* Builds subscript equality constraints. */ 321 /* Builds subscript equality constraints. */
235 322
236 static ppl_Pointset_Powerset_C_Polyhedron_t 323 static ppl_Pointset_Powerset_C_Polyhedron_t
237 dr_equality_constraints (graphite_dim_t dim, 324 dr_equality_constraints (graphite_dim_t dim,
238 graphite_dim_t pos, graphite_dim_t nb_subscripts) 325 graphite_dim_t pos, graphite_dim_t nb_subscripts)
239 { 326 {
240 ppl_Polyhedron_t subscript_equalities; 327 ppl_Polyhedron_t eqs;
241 ppl_Pointset_Powerset_C_Polyhedron_t res; 328 ppl_Pointset_Powerset_C_Polyhedron_t res;
242 Value v, v_op;
243 graphite_dim_t i; 329 graphite_dim_t i;
244 330
245 value_init (v); 331 ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0);
246 value_init (v_op); 332
247 value_set_si (v, 1);
248 value_set_si (v_op, -1);
249
250 ppl_new_C_Polyhedron_from_space_dimension (&subscript_equalities, dim, 0);
251 for (i = 0; i < nb_subscripts; i++) 333 for (i = 0; i < nb_subscripts; i++)
252 { 334 {
253 ppl_Linear_Expression_t expr; 335 ppl_Constraint_t cstr
254 ppl_Constraint_t cstr; 336 = ppl_build_relation (dim, pos + i, pos + i + nb_subscripts,
255 ppl_Coefficient_t coef; 337 0, PPL_CONSTRAINT_TYPE_EQUAL);
256 338 ppl_Polyhedron_add_constraint (eqs, cstr);
257 ppl_new_Coefficient (&coef);
258 ppl_new_Linear_Expression_with_dimension (&expr, dim);
259
260 ppl_assign_Coefficient_from_mpz_t (coef, v);
261 ppl_Linear_Expression_add_to_coefficient (expr, pos + i, coef);
262 ppl_assign_Coefficient_from_mpz_t (coef, v_op);
263 ppl_Linear_Expression_add_to_coefficient (expr, pos + i + nb_subscripts,
264 coef);
265
266 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
267 ppl_Polyhedron_add_constraint (subscript_equalities, cstr);
268
269 ppl_delete_Linear_Expression (expr);
270 ppl_delete_Constraint (cstr); 339 ppl_delete_Constraint (cstr);
271 ppl_delete_Coefficient (coef); 340 }
272 } 341
273 342 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs);
274 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 343 ppl_delete_Polyhedron (eqs);
275 (&res, subscript_equalities);
276 value_clear (v);
277 value_clear (v_op);
278 ppl_delete_Polyhedron (subscript_equalities);
279
280 return res; 344 return res;
281 } 345 }
282 346
283 /* Builds scheduling equality constraints. */ 347 /* Builds scheduling inequality constraints: when DIRECTION is
348 1 builds a GE constraint,
349 0 builds an EQ constraint,
350 -1 builds a LE constraint. */
284 351
285 static ppl_Pointset_Powerset_C_Polyhedron_t 352 static ppl_Pointset_Powerset_C_Polyhedron_t
286 build_pairwise_scheduling_equality (graphite_dim_t dim, 353 build_pairwise_scheduling (graphite_dim_t dim,
287 graphite_dim_t pos, graphite_dim_t offset) 354 graphite_dim_t pos,
355 graphite_dim_t offset,
356 int direction)
288 { 357 {
289 ppl_Pointset_Powerset_C_Polyhedron_t res; 358 ppl_Pointset_Powerset_C_Polyhedron_t res;
290 ppl_Polyhedron_t equalities; 359 ppl_Polyhedron_t equalities;
291 ppl_Constraint_t cstr; 360 ppl_Constraint_t cstr;
292 361
293 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0); 362 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
294 363
295 cstr = build_pairwise_constraint (dim, pos, pos + offset, 0, 364 switch (direction)
296 PPL_CONSTRAINT_TYPE_EQUAL); 365 {
366 case -1:
367 cstr = ppl_build_relation (dim, pos, pos + offset, 1,
368 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
369 break;
370
371 case 0:
372 cstr = ppl_build_relation (dim, pos, pos + offset, 0,
373 PPL_CONSTRAINT_TYPE_EQUAL);
374 break;
375
376 case 1:
377 cstr = ppl_build_relation (dim, pos, pos + offset, -1,
378 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
379 break;
380
381 default:
382 gcc_unreachable ();
383 }
384
297 ppl_Polyhedron_add_constraint (equalities, cstr); 385 ppl_Polyhedron_add_constraint (equalities, cstr);
298 ppl_delete_Constraint (cstr); 386 ppl_delete_Constraint (cstr);
299 387
300 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities); 388 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
301 ppl_delete_Polyhedron (equalities); 389 ppl_delete_Polyhedron (equalities);
302 return res; 390 return res;
303 } 391 }
304 392
305 /* Builds scheduling inequality constraints. */ 393 /* Add to a non empty polyhedron BAG the precedence constraints for
394 the lexicographical comparison of time vectors in BAG following the
395 lexicographical order. DIM is the dimension of the polyhedron BAG.
396 TDIM is the number of loops common to the two statements that are
397 compared lexicographically, i.e. the number of loops containing
398 both statements. OFFSET is the number of dimensions needed to
399 represent the first statement, i.e. dimT1 + dimI1 in the layout of
400 the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
401 1, compute the direct dependence from PDR1 to PDR2, and when
402 DIRECTION is -1, compute the reversed dependence relation, from
403 PDR2 to PDR1. */
306 404
307 static ppl_Pointset_Powerset_C_Polyhedron_t 405 static ppl_Pointset_Powerset_C_Polyhedron_t
308 build_pairwise_scheduling_inequality (graphite_dim_t dim, 406 build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
309 graphite_dim_t pos, 407 graphite_dim_t dim,
310 graphite_dim_t offset, 408 graphite_dim_t tdim,
311 bool direction) 409 graphite_dim_t offset,
312 { 410 int direction)
313 ppl_Pointset_Powerset_C_Polyhedron_t res; 411 {
314 ppl_Polyhedron_t equalities; 412 graphite_dim_t i;
315 ppl_Constraint_t cstr; 413 ppl_Pointset_Powerset_C_Polyhedron_t res, lex;
316 414
317 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0); 415 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1);
318 416
319 if (direction) 417 lex = build_pairwise_scheduling (dim, 0, offset, direction);
320 cstr = build_pairwise_constraint (dim, pos, pos + offset, -1, 418 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
321 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 419
322 else 420 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
323 cstr = build_pairwise_constraint (dim, pos, pos + offset, 1, 421 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
324 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); 422
325 423 ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
326 ppl_Polyhedron_add_constraint (equalities, cstr); 424
327 ppl_delete_Constraint (cstr); 425 for (i = 0; i < tdim - 1; i++)
328 426 {
329 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities); 427 ppl_Pointset_Powerset_C_Polyhedron_t sceq;
330 ppl_delete_Polyhedron (equalities); 428
429 sceq = build_pairwise_scheduling (dim, i, offset, 0);
430 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
431 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
432
433 lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
434 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
435
436 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
437 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
438
439 ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
440 }
441
331 return res; 442 return res;
332 }
333
334 /* Returns true when adding the lexicographical constraints at level I
335 to the RES dependence polyhedron returns an empty polyhedron. */
336
337 static bool
338 lexicographically_gt_p (ppl_Pointset_Powerset_C_Polyhedron_t res,
339 graphite_dim_t dim,
340 graphite_dim_t offset,
341 bool direction, graphite_dim_t i)
342 {
343 ppl_Pointset_Powerset_C_Polyhedron_t ineq;
344 bool empty_p;
345
346 ineq = build_pairwise_scheduling_inequality (dim, i, offset,
347 direction);
348 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq, res);
349 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq);
350 if (!empty_p)
351 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, ineq);
352 ppl_delete_Pointset_Powerset_C_Polyhedron (ineq);
353
354 return !empty_p;
355 }
356
357 /* Build the precedence constraints for the lexicographical comparison
358 of time vectors RES following the lexicographical order. */
359
360 static void
361 build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t *res,
362 graphite_dim_t dim,
363 graphite_dim_t tdim1,
364 graphite_dim_t offset,
365 bool direction)
366 {
367 graphite_dim_t i;
368
369 if (lexicographically_gt_p (*res, dim, offset, direction, 0))
370 return;
371
372 for (i = 0; i < tdim1 - 1; i++)
373 {
374 ppl_Pointset_Powerset_C_Polyhedron_t sceq;
375
376 sceq = build_pairwise_scheduling_equality (dim, i, offset);
377 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, sceq);
378 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
379
380 if (lexicographically_gt_p (*res, dim, offset, direction, i + 1))
381 return;
382 }
383
384 if (i == tdim1 - 1)
385 {
386 ppl_delete_Pointset_Powerset_C_Polyhedron (*res);
387 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res, dim, 1);
388 }
389 } 443 }
390 444
391 /* Build the dependence polyhedron for data references PDR1 and PDR2. 445 /* Build the dependence polyhedron for data references PDR1 and PDR2.
392 The layout of the dependence polyhedron is: 446 The layout of the dependence polyhedron is:
393 447
395 449
396 with 450 with
397 | T1 and T2 the scattering dimensions for PDR1 and PDR2 451 | T1 and T2 the scattering dimensions for PDR1 and PDR2
398 | I1 and I2 the iteration domains 452 | I1 and I2 the iteration domains
399 | S1 and S2 the subscripts 453 | S1 and S2 the subscripts
400 | G the global parameters. */ 454 | G the global parameters.
401 455
402 static poly_ddr_p 456 When DIRECTION is set to 1, compute the direct dependence from PDR1
403 dependence_polyhedron_1 (poly_bb_p pbb1, poly_bb_p pbb2, 457 to PDR2, and when DIRECTION is -1, compute the reversed dependence
404 ppl_Pointset_Powerset_C_Polyhedron_t d1, 458 relation, from PDR2 to PDR1. */
405 ppl_Pointset_Powerset_C_Polyhedron_t d2, 459
406 poly_dr_p pdr1, poly_dr_p pdr2, 460 static ppl_Pointset_Powerset_C_Polyhedron_t
407 ppl_Polyhedron_t s1, ppl_Polyhedron_t s2, 461 dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
408 bool direction, 462 int direction, bool original_scattering_p)
409 bool original_scattering_p) 463 {
410 { 464 poly_bb_p pbb1 = PDR_PBB (pdr1);
465 poly_bb_p pbb2 = PDR_PBB (pdr2);
411 scop_p scop = PBB_SCOP (pbb1); 466 scop_p scop = PBB_SCOP (pbb1);
412 graphite_dim_t tdim1 = original_scattering_p ? 467 graphite_dim_t tdim1 = original_scattering_p ?
413 pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1); 468 pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
414 graphite_dim_t tdim2 = original_scattering_p ? 469 graphite_dim_t tdim2 = original_scattering_p ?
415 pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2); 470 pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
416 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1); 471 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
417 graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2); 472 graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
418 graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1; 473 graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
474 graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
419 graphite_dim_t gdim = scop_nb_params (scop); 475 graphite_dim_t gdim = scop_nb_params (scop);
420 graphite_dim_t dim1 = pdr_dim (pdr1); 476 graphite_dim_t dim1 = pdr_dim (pdr1);
421 graphite_dim_t dim2 = pdr_dim (pdr2); 477 graphite_dim_t dim2 = pdr_dim (pdr2);
422 graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim; 478 graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim;
423 ppl_Pointset_Powerset_C_Polyhedron_t res; 479 ppl_Pointset_Powerset_C_Polyhedron_t res;
424 ppl_Pointset_Powerset_C_Polyhedron_t id1, id2, isc1, isc2, idr1, idr2; 480 ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2;
425 ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq; 481 ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
426 ppl_Pointset_Powerset_C_Polyhedron_t context;
427 482
428 gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2)); 483 gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
429 484
430 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 485 combine_context_id_scat (&sc1, pbb1, original_scattering_p);
431 (&context, SCOP_CONTEXT (scop)); 486 combine_context_id_scat (&sc2, pbb2, original_scattering_p);
432 ppl_insert_dimensions_pointset (context, 0, dim - gdim); 487
433 488 ppl_insert_dimensions_pointset (sc1, tdim1 + ddim1,
434 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, s1); 489 tdim2 + ddim2 + sdim1 + sdim2);
435 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, s2); 490
436 491 ppl_insert_dimensions_pointset (sc2, 0, tdim1 + ddim1);
437 id1 = map_into_dep_poly (dim, gdim, d1, ddim1, tdim1); 492 ppl_insert_dimensions_pointset (sc2, tdim1 + ddim1 + tdim2 + ddim2,
438 id2 = map_into_dep_poly (dim, gdim, d2, ddim2, tdim1 + ddim1 + tdim2); 493 sdim1 + sdim2);
439 isc1 = map_into_dep_poly (dim, gdim, sc1, ddim1 + tdim1, 0);
440 isc2 = map_into_dep_poly (dim, gdim, sc2, ddim2 + tdim2, tdim1 + ddim1);
441 494
442 idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim, 495 idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
443 tdim1, tdim2 + ddim2); 496 tdim1, tdim2 + ddim2);
444 idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim, 497 idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
445 tdim1 + ddim1 + tdim2, sdim1); 498 tdim1 + ddim1 + tdim2, sdim1);
446 499
447 /* Now add the subscript equalities. */ 500 /* Now add the subscript equalities. */
448 dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1); 501 dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
449 502
450 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0); 503 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
451 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, context); 504 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc1);
452 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id1); 505 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc2);
453 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id2);
454 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc1);
455 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc2);
456 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1); 506 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1);
457 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2); 507 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
458 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq); 508 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq);
459 ppl_delete_Pointset_Powerset_C_Polyhedron (context);
460 ppl_delete_Pointset_Powerset_C_Polyhedron (id1);
461 ppl_delete_Pointset_Powerset_C_Polyhedron (id2);
462 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1); 509 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
463 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2); 510 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
464 ppl_delete_Pointset_Powerset_C_Polyhedron (isc1);
465 ppl_delete_Pointset_Powerset_C_Polyhedron (isc2);
466 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1); 511 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1);
467 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2); 512 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
468 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq); 513 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
469 514
470 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res)) 515 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
471 build_lexicographically_gt_constraint (&res, dim, MIN (tdim1, tdim2), 516 {
472 tdim1 + ddim1, direction); 517 ppl_Pointset_Powerset_C_Polyhedron_t lex =
473 518 build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
474 return new_poly_ddr (pdr1, pdr2, res); 519 tdim1 + ddim1, direction);
520 ppl_delete_Pointset_Powerset_C_Polyhedron (res);
521 res = lex;
522 }
523
524 return res;
475 } 525 }
476 526
477 /* Build the dependence polyhedron for data references PDR1 and PDR2. 527 /* Build the dependence polyhedron for data references PDR1 and PDR2.
478 If possible use already cached information. */ 528 If possible use already cached information.
529
530 When DIRECTION is set to 1, compute the direct dependence from PDR1
531 to PDR2, and when DIRECTION is -1, compute the reversed dependence
532 relation, from PDR2 to PDR1. */
479 533
480 static poly_ddr_p 534 static poly_ddr_p
481 dependence_polyhedron (poly_bb_p pbb1, poly_bb_p pbb2, 535 dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
482 ppl_Pointset_Powerset_C_Polyhedron_t d1, 536 int direction, bool original_scattering_p)
483 ppl_Pointset_Powerset_C_Polyhedron_t d2,
484 poly_dr_p pdr1, poly_dr_p pdr2,
485 ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
486 bool direction,
487 bool original_scattering_p)
488 { 537 {
489 PTR *x = NULL; 538 PTR *x = NULL;
490 poly_ddr_p res; 539 poly_ddr_p res;
491 540 ppl_Pointset_Powerset_C_Polyhedron_t ddp;
541
542 /* Return the PDDR from the cache if it already has been computed. */
492 if (original_scattering_p) 543 if (original_scattering_p)
493 { 544 {
494 struct poly_ddr tmp; 545 struct poly_ddr tmp;
546 scop_p scop = PBB_SCOP (PDR_PBB (pdr1));
495 547
496 tmp.source = pdr1; 548 tmp.source = pdr1;
497 tmp.sink = pdr2; 549 tmp.sink = pdr2;
498 x = htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1)), 550 x = htab_find_slot (SCOP_ORIGINAL_PDDRS (scop),
499 &tmp, INSERT); 551 &tmp, INSERT);
500 552
501 if (x && *x) 553 if (x && *x)
502 return (poly_ddr_p) *x; 554 return (poly_ddr_p) *x;
503 } 555 }
504 556
505 res = dependence_polyhedron_1 (pbb1, pbb2, d1, d2, pdr1, pdr2, 557 if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
506 s1, s2, direction, original_scattering_p); 558 || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
559 || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
560 || !poly_drs_may_alias_p (pdr1, pdr2))
561 ddp = NULL;
562 else
563 ddp = dependence_polyhedron_1 (pdr1, pdr2, direction,
564 original_scattering_p);
565
566 res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p);
567
568 if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
569 && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
570 && poly_drs_may_alias_p (pdr1, pdr2))
571 PDDR_KIND (res) = unknown_dependence;
507 572
508 if (original_scattering_p) 573 if (original_scattering_p)
509 *x = res; 574 *x = res;
510 575
511 return res; 576 return res;
512 } 577 }
513
514 static bool
515 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2);
516
517 /* Returns the PDDR corresponding to the original schedule, or NULL if
518 the dependence relation is empty or unknown (cannot judge dependency
519 under polyhedral model). */
520
521 static poly_ddr_p
522 pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
523 poly_dr_p pdr1, poly_dr_p pdr2)
524 {
525 poly_ddr_p pddr;
526 ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
527 ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
528 ppl_Polyhedron_t so1 = PBB_ORIGINAL_SCATTERING (pbb1);
529 ppl_Polyhedron_t so2 = PBB_ORIGINAL_SCATTERING (pbb2);
530
531 if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
532 || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
533 || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
534 return NULL;
535
536 pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
537 true, true);
538 if (pddr_is_empty (pddr))
539 return NULL;
540
541 return pddr;
542 }
543
544 /* Returns the PDDR corresponding to the transformed schedule, or NULL if
545 the dependence relation is empty or unknown (cannot judge dependency
546 under polyhedral model). */
547
548 static poly_ddr_p
549 pddr_transformed_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
550 poly_dr_p pdr1, poly_dr_p pdr2)
551 {
552 poly_ddr_p pddr;
553 ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
554 ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
555 ppl_Polyhedron_t st1 = PBB_ORIGINAL_SCATTERING (pbb1);
556 ppl_Polyhedron_t st2 = PBB_ORIGINAL_SCATTERING (pbb2);
557
558 if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
559 || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
560 || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
561 return NULL;
562
563 pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
564 true, false);
565 if (pddr_is_empty (pddr))
566 return NULL;
567
568 return pddr;
569 }
570
571 578
572 /* Return true when the data dependence relation between the data 579 /* Return true when the data dependence relation between the data
573 references PDR1 belonging to PBB1 and PDR2 is part of a 580 references PDR1 belonging to PBB1 and PDR2 is part of a
574 reduction. */ 581 reduction. */
575 582
589 /* Return true when the data dependence relation between the data 596 /* Return true when the data dependence relation between the data
590 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is 597 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
591 part of a reduction. */ 598 part of a reduction. */
592 599
593 static inline bool 600 static inline bool
594 reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2, 601 reduction_dr_p (poly_dr_p pdr1, poly_dr_p pdr2)
595 poly_dr_p pdr1, poly_dr_p pdr2) 602 {
596 { 603 poly_bb_p pbb1 = PDR_PBB (pdr1);
604 poly_bb_p pbb2 = PDR_PBB (pdr2);
605
597 if (PBB_IS_REDUCTION (pbb1)) 606 if (PBB_IS_REDUCTION (pbb1))
598 return reduction_dr_1 (pbb1, pdr1, pdr2); 607 return reduction_dr_1 (pbb1, pdr1, pdr2);
599 608
600 if (PBB_IS_REDUCTION (pbb2)) 609 if (PBB_IS_REDUCTION (pbb2))
601 return reduction_dr_1 (pbb2, pdr2, pdr1); 610 return reduction_dr_1 (pbb2, pdr2, pdr1);
606 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1 615 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
607 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING 616 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
608 functions. */ 617 functions. */
609 618
610 static bool 619 static bool
611 graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2, 620 graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
612 poly_dr_p pdr1, poly_dr_p pdr2) 621 {
613 {
614 ppl_Polyhedron_t st1, st2;
615 ppl_Pointset_Powerset_C_Polyhedron_t po, pt; 622 ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
616 graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2; 623 graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
617 ppl_Pointset_Powerset_C_Polyhedron_t temp; 624 ppl_Pointset_Powerset_C_Polyhedron_t po_temp;
618 ppl_dimension_type pdim; 625 ppl_dimension_type pdim;
619 bool is_empty_p; 626 bool is_empty_p;
620 poly_ddr_p pddr; 627 poly_ddr_p opddr, tpddr;
621 ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1); 628 poly_bb_p pbb1, pbb2;
622 ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2); 629
623 630 if (reduction_dr_p (pdr1, pdr2))
624 if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
625 return true; 631 return true;
626 632
627 pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2); 633 /* We build the reverse dependence relation for the transformed
628 if (!pddr) 634 scattering, such that when we intersect it with the original PO,
635 we get an empty intersection when the transform is legal:
636 i.e. the transform should reverse no dependences, and so PT, the
637 reversed transformed PDDR, should have no constraint from PO. */
638 opddr = dependence_polyhedron (pdr1, pdr2, 1, true);
639
640 if (PDDR_KIND (opddr) == unknown_dependence)
641 return false;
642
643 /* There are no dependences between PDR1 and PDR2 in the original
644 version of the program, or after the transform, so the
645 transform is legal. */
646 if (pddr_is_empty (opddr))
629 return true; 647 return true;
630 648
631 po = PDDR_DDP (pddr); 649 tpddr = dependence_polyhedron (pdr1, pdr2, -1, false);
632 650
633 if (dump_file && (dump_flags & TDF_DETAILS)) 651 if (PDDR_KIND (tpddr) == unknown_dependence)
634 fprintf (dump_file, "\nloop carries dependency.\n"); 652 {
635 653 free_poly_ddr (tpddr);
636 st1 = PBB_TRANSFORMED_SCATTERING (pbb1); 654 return false;
637 st2 = PBB_TRANSFORMED_SCATTERING (pbb2); 655 }
656
657 if (pddr_is_empty (tpddr))
658 {
659 free_poly_ddr (tpddr);
660 return true;
661 }
662
663 po = PDDR_DDP (opddr);
664 pt = PDDR_DDP (tpddr);
665
666 /* Copy PO into PO_TEMP, such that PO is not destroyed. PO is
667 stored in a cache and should not be modified or freed. */
668 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
669 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp,
670 pdim, 0);
671 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, po);
672
673 /* Extend PO and PT to have the same dimensions. */
674 pbb1 = PDR_PBB (pdr1);
675 pbb2 = PDR_PBB (pdr2);
638 ddim1 = pbb_dim_iter_domain (pbb1); 676 ddim1 = pbb_dim_iter_domain (pbb1);
639 otdim1 = pbb_nb_scattering_orig (pbb1); 677 otdim1 = pbb_nb_scattering_orig (pbb1);
640 otdim2 = pbb_nb_scattering_orig (pbb2); 678 otdim2 = pbb_nb_scattering_orig (pbb2);
641 ttdim1 = pbb_nb_scattering_transform (pbb1); 679 ttdim1 = pbb_nb_scattering_transform (pbb1);
642 ttdim2 = pbb_nb_scattering_transform (pbb2); 680 ttdim2 = pbb_nb_scattering_transform (pbb2);
643 681 ppl_insert_dimensions_pointset (po_temp, otdim1, ttdim1);
644 /* Copy the PO polyhedron into the TEMP, so it is not destroyed. 682 ppl_insert_dimensions_pointset (po_temp, otdim1 + ttdim1 + ddim1 + otdim2,
645 Keep in mind, that PO polyhedron might be restored from the cache 683 ttdim2);
646 and should not be modified! */
647 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
648 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp, pdim, 0);
649 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, po);
650
651 pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
652 false, false);
653 pt = PDDR_DDP (pddr);
654
655 /* Extend PO and PT to have the same dimensions. */
656 ppl_insert_dimensions_pointset (temp, otdim1, ttdim1);
657 ppl_insert_dimensions_pointset (temp, otdim1 + ttdim1 + ddim1 + otdim2, ttdim2);
658 ppl_insert_dimensions_pointset (pt, 0, otdim1); 684 ppl_insert_dimensions_pointset (pt, 0, otdim1);
659 ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2); 685 ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
660 686
661 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, pt); 687 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
662 is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp); 688 is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
663 689
664 ppl_delete_Pointset_Powerset_C_Polyhedron (temp); 690 ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
665 free_poly_ddr (pddr); 691 free_poly_ddr (tpddr);
692
693 if (dump_file && (dump_flags & TDF_DETAILS))
694 fprintf (dump_file, "\nloop carries dependency.\n");
666 695
667 return is_empty_p; 696 return is_empty_p;
668 } 697 }
669 698
670 /* Return true when the data dependence relation for PBB1 and PBB2 is 699 /* Return true when the data dependence relation for PBB1 and PBB2 is
694 if (reduction_ddr_p (pbb1, pbb2)) 723 if (reduction_ddr_p (pbb1, pbb2))
695 return true; 724 return true;
696 725
697 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++) 726 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
698 for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++) 727 for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
699 if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2)) 728 if (!graphite_legal_transform_dr (pdr1, pdr2))
700 return false; 729 return false;
701 730
702 return true; 731 return true;
703 } 732 }
704 733
723 752
724 timevar_pop (TV_GRAPHITE_DATA_DEPS); 753 timevar_pop (TV_GRAPHITE_DATA_DEPS);
725 return true; 754 return true;
726 } 755 }
727 756
728 /* Remove all the dimensions except alias information at dimension
729 ALIAS_DIM. */
730
731 static void
732 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
733 ppl_dimension_type alias_dim)
734 {
735 ppl_dimension_type *ds;
736 ppl_dimension_type access_dim;
737 unsigned i, pos = 0;
738
739 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
740 &access_dim);
741 ds = XNEWVEC (ppl_dimension_type, access_dim-1);
742 for (i = 0; i < access_dim; i++)
743 {
744 if (i == alias_dim)
745 continue;
746
747 ds[pos] = i;
748 pos++;
749 }
750
751 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
752 ds,
753 access_dim - 1);
754 free (ds);
755 }
756
757 /* Return true when PDR1 and PDR2 may alias. */
758
759 static bool
760 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
761 {
762 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
763 ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
764 ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
765 ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
766 ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
767 int empty_p;
768
769 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
770 (&alias_powerset1, accesses1);
771 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
772 (&alias_powerset2, accesses2);
773
774 build_alias_set_powerset (alias_powerset1, alias_dim1);
775 build_alias_set_powerset (alias_powerset2, alias_dim2);
776
777 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
778 (alias_powerset1, alias_powerset2);
779
780 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
781
782 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
783 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
784
785 return !empty_p;
786 }
787
788 /* Returns TRUE when the dependence polyhedron between PDR1 and 757 /* Returns TRUE when the dependence polyhedron between PDR1 and
789 PDR2 represents a loop carried dependence at level LEVEL. */ 758 PDR2 represents a loop carried dependence at level LEVEL. */
790 759
791 static bool 760 static bool
792 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2, 761 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
793 int level) 762 int level)
794 { 763 {
795 poly_bb_p pbb1 = PDR_PBB (pdr1);
796 poly_bb_p pbb2 = PDR_PBB (pdr2);
797 ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
798 ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
799 ppl_Polyhedron_t so1 = PBB_TRANSFORMED_SCATTERING (pbb1);
800 ppl_Polyhedron_t so2 = PBB_TRANSFORMED_SCATTERING (pbb2);
801 ppl_Pointset_Powerset_C_Polyhedron_t po; 764 ppl_Pointset_Powerset_C_Polyhedron_t po;
802 ppl_Pointset_Powerset_C_Polyhedron_t eqpp; 765 ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
803 graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1); 766 graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1));
804 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1); 767 graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1));
805 ppl_dimension_type dim; 768 ppl_dimension_type dim;
806 bool empty_p; 769 bool empty_p;
807 poly_ddr_p pddr; 770 poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
808 int obj_base_set1 = PDR_BASE_OBJECT_SET (pdr1); 771
809 int obj_base_set2 = PDR_BASE_OBJECT_SET (pdr2); 772 if (PDDR_KIND (pddr) == unknown_dependence)
810 773 {
811 if ((pdr_read_p (pdr1) && pdr_read_p (pdr2)) 774 free_poly_ddr (pddr);
812 || !poly_drs_may_alias_p (pdr1, pdr2)) 775 return true;
813 return false; 776 }
814
815 if (obj_base_set1 != obj_base_set2)
816 return true;
817
818 if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
819 return false;
820
821 pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
822 true, false);
823 777
824 if (pddr_is_empty (pddr)) 778 if (pddr_is_empty (pddr))
825 return false; 779 {
780 free_poly_ddr (pddr);
781 return false;
782 }
826 783
827 po = PDDR_DDP (pddr); 784 po = PDDR_DDP (pddr);
828 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim); 785 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
829 eqpp = build_pairwise_scheduling_inequality (dim, level, tdim1 + ddim1, 1); 786 eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1);
830 787
831 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po); 788 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
832 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp); 789 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
833 790
834 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp); 791 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
792 free_poly_ddr (pddr);
793
835 return !empty_p; 794 return !empty_p;
836 } 795 }
837 796
838 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */ 797 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
839 798
870 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) 829 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
871 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) 830 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
872 { 831 {
873 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) 832 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
874 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) 833 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
875 if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2)) 834 if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
876 { 835 {
877 fprintf (file, "OS%d -> OS%d\n", 836 fprintf (file, "OS%d -> OS%d\n",
878 pbb_index (pbb1), pbb_index (pbb2)); 837 pbb_index (pbb1), pbb_index (pbb2));
879 goto done; 838 goto done;
880 } 839 }
895 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) 854 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
896 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) 855 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
897 { 856 {
898 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) 857 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
899 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) 858 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
900 if (pddr_transformed_scattering (pbb1, pbb2, pdr1, pdr2)) 859 {
901 { 860 poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
902 fprintf (file, "TS%d -> TS%d\n", 861
903 pbb_index (pbb1), pbb_index (pbb2)); 862 if (!pddr_is_empty (pddr))
904 goto done; 863 {
905 } 864 fprintf (file, "TS%d -> TS%d\n",
865 pbb_index (pbb1), pbb_index (pbb2));
866
867 free_poly_ddr (pddr);
868 goto done;
869 }
870
871 free_poly_ddr (pddr);
872 }
906 done:; 873 done:;
907 } 874 }
908 } 875 }
909 876
910 877
934 901
935 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) 902 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
936 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) 903 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
937 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) 904 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
938 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) 905 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
939 if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2)) 906 if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
940 fprintf (file, "OS%d_D%d -> OS%d_D%d\n", 907 fprintf (file, "OS%d_D%d -> OS%d_D%d\n",
941 pbb_index (pbb1), PDR_ID (pdr1), 908 pbb_index (pbb1), PDR_ID (pdr1),
942 pbb_index (pbb2), PDR_ID (pdr2)); 909 pbb_index (pbb2), PDR_ID (pdr2));
943 } 910 }
944 911
954 921
955 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) 922 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
956 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) 923 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
957 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) 924 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
958 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) 925 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
959 if (pddr_transformed_scattering (pbb1, pbb2, pdr1, pdr2)) 926 {
960 fprintf (file, "TS%d_D%d -> TS%d_D%d\n", 927 poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
961 pbb_index (pbb1), PDR_ID (pdr1), 928
962 pbb_index (pbb2), PDR_ID (pdr2)); 929 if (!pddr_is_empty (pddr))
930 fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
931 pbb_index (pbb1), PDR_ID (pdr1),
932 pbb_index (pbb2), PDR_ID (pdr2));
933
934 free_poly_ddr (pddr);
935 }
963 } 936 }
964 937
965 /* Pretty print to FILE all the data dependences of SCoP in DOT 938 /* Pretty print to FILE all the data dependences of SCoP in DOT
966 format. */ 939 format. */
967 940