Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-dependences.c @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents
children b7f97abdc517
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Konrad Trifunovic <konrad.trifunovic@inria.fr>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "toplev.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
40 #include "domwalk.h"
41 #include "pointer-set.h"
42 #include "gimple.h"
43
44 #ifdef HAVE_cloog
45 #include "cloog/cloog.h"
46 #include "ppl_c.h"
47 #include "sese.h"
48 #include "graphite-ppl.h"
49 #include "graphite.h"
50 #include "graphite-poly.h"
51 #include "graphite-dependences.h"
52
53 /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is
54 the source data reference, SINK is the sink data reference. SOURCE
55 and SINK define an edge in the Data Dependence Graph (DDG). */
56
57 static poly_ddr_p
58 new_poly_ddr (poly_dr_p source, poly_dr_p sink,
59 ppl_Pointset_Powerset_C_Polyhedron_t ddp)
60 {
61 poly_ddr_p pddr;
62
63 pddr = XNEW (struct poly_ddr);
64 PDDR_SOURCE (pddr) = source;
65 PDDR_SINK (pddr) = sink;
66 PDDR_DDP (pddr) = ddp;
67 PDDR_KIND (pddr) = unknown_dependence;
68
69 return pddr;
70 }
71
72 /* Free the poly_ddr_p P. */
73
74 void
75 free_poly_ddr (void *p)
76 {
77 poly_ddr_p pddr = (poly_ddr_p) p;
78 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
79 free (pddr);
80 }
81
82 /* Comparison function for poly_ddr hash table. */
83
84 int
85 eq_poly_ddr_p (const void *pddr1, const void *pddr2)
86 {
87 const struct poly_ddr *p1 = (const struct poly_ddr *) pddr1;
88 const struct poly_ddr *p2 = (const struct poly_ddr *) pddr2;
89
90 return (PDDR_SOURCE (p1) == PDDR_SOURCE (p2)
91 && PDDR_SINK (p1) == PDDR_SINK (p2));
92 }
93
94 /* Hash function for poly_ddr hashtable. */
95
96 hashval_t
97 hash_poly_ddr_p (const void *pddr)
98 {
99 const struct poly_ddr *p = (const struct poly_ddr *) pddr;
100
101 return (hashval_t) ((long) PDDR_SOURCE (p) + (long) PDDR_SINK (p));
102 }
103
104 /* Returns true when PDDR has no dependence. */
105
106 static bool
107 pddr_is_empty (poly_ddr_p pddr)
108 {
109 if (PDDR_KIND (pddr) != unknown_dependence)
110 return PDDR_KIND (pddr) == no_dependence ? true : false;
111
112 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PDDR_DDP (pddr)))
113 {
114 PDDR_KIND (pddr) = no_dependence;
115 return true;
116 }
117
118 PDDR_KIND (pddr) = has_dependence;
119 return false;
120 }
121
122 /* Returns a polyhedron of dimension DIM.
123
124 Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET
125 and the dimensions [cut, ..., nb_dim] to DIM - GDIM. */
126
127 static ppl_Pointset_Powerset_C_Polyhedron_t
128 map_into_dep_poly (graphite_dim_t dim, graphite_dim_t gdim,
129 ppl_Pointset_Powerset_C_Polyhedron_t p,
130 graphite_dim_t cut,
131 graphite_dim_t offset)
132 {
133 ppl_Pointset_Powerset_C_Polyhedron_t res;
134
135 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
136 (&res, p);
137 ppl_insert_dimensions_pointset (res, 0, offset);
138 ppl_insert_dimensions_pointset (res, offset + cut,
139 dim - offset - cut - gdim);
140
141 return res;
142 }
143
144 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
145 transformed into "a CUT0 c CUT1' b"
146
147 Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b"
148 Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b"
149 Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
150 "00...0 a 00...0 c 00...0 b". */
151
152 static ppl_Pointset_Powerset_C_Polyhedron_t
153 map_dr_into_dep_poly (graphite_dim_t dim,
154 ppl_Pointset_Powerset_C_Polyhedron_t dr,
155 graphite_dim_t cut0, graphite_dim_t cut1,
156 graphite_dim_t nb0, graphite_dim_t nb1)
157 {
158 ppl_dimension_type pdim;
159 ppl_dimension_type *map;
160 ppl_Pointset_Powerset_C_Polyhedron_t res;
161 ppl_dimension_type i;
162
163 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
164 (&res, dr);
165 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim);
166
167 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim);
168
169 /* First mapping: move 'g' vector to right position. */
170 for (i = 0; i < cut0; i++)
171 map[i] = i;
172
173 for (i = cut0; i < cut1; i++)
174 map[i] = pdim - cut1 + i;
175
176 for (i = cut1; i < pdim; i++)
177 map[i] = cut0 + i - cut1;
178
179 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim);
180 free (map);
181
182 /* After swapping 's' and 'g' vectors, we have to update a new cut. */
183 cut1 = pdim - cut1 + cut0;
184
185 ppl_insert_dimensions_pointset (res, 0, nb0);
186 ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1);
187 ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1,
188 dim - nb0 - nb1 - pdim);
189
190 return res;
191 }
192
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. */
235
236 static ppl_Pointset_Powerset_C_Polyhedron_t
237 dr_equality_constraints (graphite_dim_t dim,
238 graphite_dim_t pos, graphite_dim_t nb_subscripts)
239 {
240 ppl_Polyhedron_t subscript_equalities;
241 ppl_Pointset_Powerset_C_Polyhedron_t res;
242 Value v, v_op;
243 graphite_dim_t i;
244
245 value_init (v);
246 value_init (v_op);
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++)
252 {
253 ppl_Linear_Expression_t expr;
254 ppl_Constraint_t cstr;
255 ppl_Coefficient_t coef;
256
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);
271 ppl_delete_Coefficient (coef);
272 }
273
274 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
275 (&res, subscript_equalities);
276 value_clear (v);
277 value_clear (v_op);
278 ppl_delete_Polyhedron (subscript_equalities);
279
280 return res;
281 }
282
283 /* Builds scheduling equality constraints. */
284
285 static ppl_Pointset_Powerset_C_Polyhedron_t
286 build_pairwise_scheduling_equality (graphite_dim_t dim,
287 graphite_dim_t pos, graphite_dim_t offset)
288 {
289 ppl_Pointset_Powerset_C_Polyhedron_t res;
290 ppl_Polyhedron_t equalities;
291 ppl_Constraint_t cstr;
292
293 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
294
295 cstr = build_pairwise_constraint (dim, pos, pos + offset, 0,
296 PPL_CONSTRAINT_TYPE_EQUAL);
297 ppl_Polyhedron_add_constraint (equalities, cstr);
298 ppl_delete_Constraint (cstr);
299
300 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
301 ppl_delete_Polyhedron (equalities);
302 return res;
303 }
304
305 /* Builds scheduling inequality constraints. */
306
307 static ppl_Pointset_Powerset_C_Polyhedron_t
308 build_pairwise_scheduling_inequality (graphite_dim_t dim,
309 graphite_dim_t pos,
310 graphite_dim_t offset,
311 bool direction)
312 {
313 ppl_Pointset_Powerset_C_Polyhedron_t res;
314 ppl_Polyhedron_t equalities;
315 ppl_Constraint_t cstr;
316
317 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
318
319 if (direction)
320 cstr = build_pairwise_constraint (dim, pos, pos + offset, -1,
321 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
322 else
323 cstr = build_pairwise_constraint (dim, pos, pos + offset, 1,
324 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
325
326 ppl_Polyhedron_add_constraint (equalities, cstr);
327 ppl_delete_Constraint (cstr);
328
329 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
330 ppl_delete_Polyhedron (equalities);
331 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 }
390
391 /* Build the dependence polyhedron for data references PDR1 and PDR2.
392 The layout of the dependence polyhedron is:
393
394 T1|I1|T2|I2|S1|S2|G
395
396 with
397 | T1 and T2 the scattering dimensions for PDR1 and PDR2
398 | I1 and I2 the iteration domains
399 | S1 and S2 the subscripts
400 | G the global parameters. */
401
402 static poly_ddr_p
403 dependence_polyhedron_1 (poly_bb_p pbb1, poly_bb_p pbb2,
404 ppl_Pointset_Powerset_C_Polyhedron_t d1,
405 ppl_Pointset_Powerset_C_Polyhedron_t d2,
406 poly_dr_p pdr1, poly_dr_p pdr2,
407 ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
408 bool direction,
409 bool original_scattering_p)
410 {
411 scop_p scop = PBB_SCOP (pbb1);
412 graphite_dim_t tdim1 = original_scattering_p ?
413 pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
414 graphite_dim_t tdim2 = original_scattering_p ?
415 pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
416 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
417 graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
418 graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
419 graphite_dim_t gdim = scop_nb_params (scop);
420 graphite_dim_t dim1 = pdr_dim (pdr1);
421 graphite_dim_t dim2 = pdr_dim (pdr2);
422 graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim;
423 ppl_Pointset_Powerset_C_Polyhedron_t res;
424 ppl_Pointset_Powerset_C_Polyhedron_t id1, id2, isc1, isc2, idr1, idr2;
425 ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
426 ppl_Pointset_Powerset_C_Polyhedron_t context;
427
428 gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
429
430 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
431 (&context, SCOP_CONTEXT (scop));
432 ppl_insert_dimensions_pointset (context, 0, dim - gdim);
433
434 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, s1);
435 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, s2);
436
437 id1 = map_into_dep_poly (dim, gdim, d1, ddim1, tdim1);
438 id2 = map_into_dep_poly (dim, gdim, d2, ddim2, tdim1 + ddim1 + tdim2);
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
442 idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
443 tdim1, tdim2 + ddim2);
444 idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
445 tdim1 + ddim1 + tdim2, sdim1);
446
447 /* Now add the subscript equalities. */
448 dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
449
450 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
451 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, context);
452 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id1);
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);
457 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
458 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);
463 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);
467 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
468 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
469
470 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
471 build_lexicographically_gt_constraint (&res, dim, MIN (tdim1, tdim2),
472 tdim1 + ddim1, direction);
473
474 return new_poly_ddr (pdr1, pdr2, res);
475 }
476
477 /* Build the dependence polyhedron for data references PDR1 and PDR2.
478 If possible use already cached information. */
479
480 static poly_ddr_p
481 dependence_polyhedron (poly_bb_p pbb1, poly_bb_p pbb2,
482 ppl_Pointset_Powerset_C_Polyhedron_t d1,
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 {
489 PTR *x = NULL;
490 poly_ddr_p res;
491
492 if (original_scattering_p)
493 {
494 struct poly_ddr tmp;
495
496 tmp.source = pdr1;
497 tmp.sink = pdr2;
498 x = htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1)),
499 &tmp, INSERT);
500
501 if (x && *x)
502 return (poly_ddr_p) *x;
503 }
504
505 res = dependence_polyhedron_1 (pbb1, pbb2, d1, d2, pdr1, pdr2,
506 s1, s2, direction, original_scattering_p);
507
508 if (original_scattering_p)
509 *x = res;
510
511 return res;
512 }
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
572 /* Return true when the data dependence relation between the data
573 references PDR1 belonging to PBB1 and PDR2 is part of a
574 reduction. */
575
576 static inline bool
577 reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
578 {
579 int i;
580 poly_dr_p pdr;
581
582 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
583 if (PDR_TYPE (pdr) == PDR_WRITE)
584 break;
585
586 return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
587 }
588
589 /* Return true when the data dependence relation between the data
590 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
591 part of a reduction. */
592
593 static inline bool
594 reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2,
595 poly_dr_p pdr1, poly_dr_p pdr2)
596 {
597 if (PBB_IS_REDUCTION (pbb1))
598 return reduction_dr_1 (pbb1, pdr1, pdr2);
599
600 if (PBB_IS_REDUCTION (pbb2))
601 return reduction_dr_1 (pbb2, pdr2, pdr1);
602
603 return false;
604 }
605
606 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
607 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
608 functions. */
609
610 static bool
611 graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
612 poly_dr_p pdr1, poly_dr_p pdr2)
613 {
614 ppl_Polyhedron_t st1, st2;
615 ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
616 graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
617 ppl_Pointset_Powerset_C_Polyhedron_t temp;
618 ppl_dimension_type pdim;
619 bool is_empty_p;
620 poly_ddr_p pddr;
621 ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
622 ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
623
624 if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
625 return true;
626
627 pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2);
628 if (!pddr)
629 return true;
630
631 po = PDDR_DDP (pddr);
632
633 if (dump_file && (dump_flags & TDF_DETAILS))
634 fprintf (dump_file, "\nloop carries dependency.\n");
635
636 st1 = PBB_TRANSFORMED_SCATTERING (pbb1);
637 st2 = PBB_TRANSFORMED_SCATTERING (pbb2);
638 ddim1 = pbb_dim_iter_domain (pbb1);
639 otdim1 = pbb_nb_scattering_orig (pbb1);
640 otdim2 = pbb_nb_scattering_orig (pbb2);
641 ttdim1 = pbb_nb_scattering_transform (pbb1);
642 ttdim2 = pbb_nb_scattering_transform (pbb2);
643
644 /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
645 Keep in mind, that PO polyhedron might be restored from the cache
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);
659 ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
660
661 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, pt);
662 is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp);
663
664 ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
665 free_poly_ddr (pddr);
666
667 return is_empty_p;
668 }
669
670 /* Return true when the data dependence relation for PBB1 and PBB2 is
671 part of a reduction. */
672
673 static inline bool
674 reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
675 {
676 return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
677 }
678
679 /* Iterates over the data references of PBB1 and PBB2 and detect
680 whether the transformed schedule is correct. */
681
682 static bool
683 graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
684 {
685 int i, j;
686 poly_dr_p pdr1, pdr2;
687
688 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
689 pbb_remove_duplicate_pdrs (pbb1);
690
691 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
692 pbb_remove_duplicate_pdrs (pbb2);
693
694 if (reduction_ddr_p (pbb1, pbb2))
695 return true;
696
697 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++)
699 if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
700 return false;
701
702 return true;
703 }
704
705 /* Iterates over the SCOP and detect whether the transformed schedule
706 is correct. */
707
708 bool
709 graphite_legal_transform (scop_p scop)
710 {
711 int i, j;
712 poly_bb_p pbb1, pbb2;
713
714 timevar_push (TV_GRAPHITE_DATA_DEPS);
715
716 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
717 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
718 if (!graphite_legal_transform_bb (pbb1, pbb2))
719 {
720 timevar_pop (TV_GRAPHITE_DATA_DEPS);
721 return false;
722 }
723
724 timevar_pop (TV_GRAPHITE_DATA_DEPS);
725 return true;
726 }
727
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
789 PDR2 represents a loop carried dependence at level LEVEL. */
790
791 static bool
792 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
793 int level)
794 {
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;
802 ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
803 graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
804 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
805 ppl_dimension_type dim;
806 bool empty_p;
807 poly_ddr_p pddr;
808 int obj_base_set1 = PDR_BASE_OBJECT_SET (pdr1);
809 int obj_base_set2 = PDR_BASE_OBJECT_SET (pdr2);
810
811 if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
812 || !poly_drs_may_alias_p (pdr1, pdr2))
813 return false;
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
824 if (pddr_is_empty (pddr))
825 return false;
826
827 po = PDDR_DDP (pddr);
828 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
829 eqpp = build_pairwise_scheduling_inequality (dim, level, tdim1 + ddim1, 1);
830
831 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
832 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
833
834 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
835 return !empty_p;
836 }
837
838 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
839
840 bool
841 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
842 {
843 int i, j;
844 poly_dr_p pdr1, pdr2;
845
846 timevar_push (TV_GRAPHITE_DATA_DEPS);
847
848 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
849 for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
850 if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
851 {
852 timevar_pop (TV_GRAPHITE_DATA_DEPS);
853 return true;
854 }
855
856 timevar_pop (TV_GRAPHITE_DATA_DEPS);
857 return false;
858 }
859
860 /* Pretty print to FILE all the original data dependences of SCoP in
861 DOT format. */
862
863 static void
864 dot_original_deps_stmt_1 (FILE *file, scop_p scop)
865 {
866 int i, j, k, l;
867 poly_bb_p pbb1, pbb2;
868 poly_dr_p pdr1, pdr2;
869
870 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++)
872 {
873 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++)
875 if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2))
876 {
877 fprintf (file, "OS%d -> OS%d\n",
878 pbb_index (pbb1), pbb_index (pbb2));
879 goto done;
880 }
881 done:;
882 }
883 }
884
885 /* Pretty print to FILE all the transformed data dependences of SCoP in
886 DOT format. */
887
888 static void
889 dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
890 {
891 int i, j, k, l;
892 poly_bb_p pbb1, pbb2;
893 poly_dr_p pdr1, pdr2;
894
895 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++)
897 {
898 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++)
900 if (pddr_transformed_scattering (pbb1, pbb2, pdr1, pdr2))
901 {
902 fprintf (file, "TS%d -> TS%d\n",
903 pbb_index (pbb1), pbb_index (pbb2));
904 goto done;
905 }
906 done:;
907 }
908 }
909
910
911 /* Pretty print to FILE all the data dependences of SCoP in DOT
912 format. */
913
914 static void
915 dot_deps_stmt_1 (FILE *file, scop_p scop)
916 {
917 fputs ("digraph all {\n", file);
918
919 dot_original_deps_stmt_1 (file, scop);
920 dot_transformed_deps_stmt_1 (file, scop);
921
922 fputs ("}\n\n", file);
923 }
924
925 /* Pretty print to FILE all the original data dependences of SCoP in
926 DOT format. */
927
928 static void
929 dot_original_deps (FILE *file, scop_p scop)
930 {
931 int i, j, k, l;
932 poly_bb_p pbb1, pbb2;
933 poly_dr_p pdr1, pdr2;
934
935 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++)
937 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++)
939 if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2))
940 fprintf (file, "OS%d_D%d -> OS%d_D%d\n",
941 pbb_index (pbb1), PDR_ID (pdr1),
942 pbb_index (pbb2), PDR_ID (pdr2));
943 }
944
945 /* Pretty print to FILE all the transformed data dependences of SCoP in
946 DOT format. */
947
948 static void
949 dot_transformed_deps (FILE *file, scop_p scop)
950 {
951 int i, j, k, l;
952 poly_bb_p pbb1, pbb2;
953 poly_dr_p pdr1, pdr2;
954
955 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++)
957 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++)
959 if (pddr_transformed_scattering (pbb1, pbb2, pdr1, pdr2))
960 fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
961 pbb_index (pbb1), PDR_ID (pdr1),
962 pbb_index (pbb2), PDR_ID (pdr2));
963 }
964
965 /* Pretty print to FILE all the data dependences of SCoP in DOT
966 format. */
967
968 static void
969 dot_deps_1 (FILE *file, scop_p scop)
970 {
971 fputs ("digraph all {\n", file);
972
973 dot_original_deps (file, scop);
974 dot_transformed_deps (file, scop);
975
976 fputs ("}\n\n", file);
977 }
978
979 /* Display all the data dependences in SCoP using dotty. */
980
981 void
982 dot_deps (scop_p scop)
983 {
984 /* When debugging, enable the following code. This cannot be used
985 in production compilers because it calls "system". */
986 #if 0
987 int x;
988 FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
989 gcc_assert (stream);
990
991 dot_deps_1 (stream, scop);
992 fclose (stream);
993
994 x = system ("dotty /tmp/scopdeps.dot");
995 #else
996 dot_deps_1 (stderr, scop);
997 #endif
998 }
999
1000 /* Display all the statement dependences in SCoP using dotty. */
1001
1002 void
1003 dot_deps_stmt (scop_p scop)
1004 {
1005 /* When debugging, enable the following code. This cannot be used
1006 in production compilers because it calls "system". */
1007 #if 0
1008 int x;
1009 FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
1010 gcc_assert (stream);
1011
1012 dot_deps_stmt_1 (stream, scop);
1013 fclose (stream);
1014
1015 x = system ("dotty /tmp/scopdeps.dot");
1016 #else
1017 dot_deps_stmt_1 (stderr, scop);
1018 #endif
1019 }
1020
1021 #endif