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>.
6 This file is part of GCC.
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)
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.
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/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
41 #include "pointer-set.h"
45 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-dependences.h"
53 /* Creates a new polyhedral data reference pair and
54 returns it. Parameter SOURCE denotes a source data reference
55 while parameter SINK denotes a sink data reference. Both
56 SOURCE and SINK define a pair of references, thus they
57 define an edge in DDG (Data Dependence Graph). */
60 new_poly_dr_pair (poly_dr_p source
,
62 ppl_Pointset_Powerset_C_Polyhedron_t ddp
)
66 pdrpp
= XNEW (struct poly_dr_pair
);
67 pdrpp
->source
= source
;
74 /* Comparison function for poly_dr_pair hash table. */
77 eq_poly_dr_pair_p (const void *pdrpp1
, const void *pdrpp2
)
79 const struct poly_dr_pair
*p1
= (const struct poly_dr_pair
*) pdrpp1
;
80 const struct poly_dr_pair
*p2
= (const struct poly_dr_pair
*) pdrpp2
;
82 return (p1
->source
== p2
->source
83 && p1
->sink
== p2
->sink
);
86 /* Hash function for poly_dr_pair hashtable. */
89 hash_poly_dr_pair_p (const void *pdrpp
)
91 const struct poly_dr_pair
*p
= (const struct poly_dr_pair
*) pdrpp
;
93 return (hashval_t
) ((long) p
->source
+ (long) p
->sink
);
96 /* Returns a polyhedron of dimension DIM.
98 Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET0
99 and the dimensions [cut, ..., nb_dim] to DIM - GDIM. */
101 static ppl_Pointset_Powerset_C_Polyhedron_t
102 map_into_dep_poly (graphite_dim_t dim
, graphite_dim_t gdim
,
103 ppl_Pointset_Powerset_C_Polyhedron_t p
,
105 graphite_dim_t offset
)
107 ppl_Pointset_Powerset_C_Polyhedron_t res
;
109 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
111 ppl_insert_dimensions_pointset (res
, 0, offset
);
112 ppl_insert_dimensions_pointset (res
, offset
+ cut
,
113 dim
- offset
- cut
- gdim
);
118 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
119 transformed into "a CUT0 c CUT1' b"
121 Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b"
122 Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b"
123 Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
124 "00...0 a 00...0 c 00...0 b". */
126 static ppl_Pointset_Powerset_C_Polyhedron_t
127 map_dr_into_dep_poly (graphite_dim_t dim
,
128 ppl_Pointset_Powerset_C_Polyhedron_t dr
,
129 graphite_dim_t cut0
, graphite_dim_t cut1
,
130 graphite_dim_t nb0
, graphite_dim_t nb1
)
132 ppl_dimension_type pdim
;
133 ppl_dimension_type
*map
;
134 ppl_Pointset_Powerset_C_Polyhedron_t res
;
135 ppl_dimension_type i
;
137 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
139 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res
, &pdim
);
141 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, pdim
);
143 /* First mapping: move 'g' vector to right position. */
144 for (i
= 0; i
< cut0
; i
++)
147 for (i
= cut0
; i
< cut1
; i
++)
148 map
[i
] = pdim
- cut1
+ i
;
150 for (i
= cut1
; i
< pdim
; i
++)
151 map
[i
] = cut0
+ i
- cut1
;
153 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res
, map
, pdim
);
156 /* After swapping 's' and 'g' vectors, we have to update a new cut. */
157 cut1
= pdim
- cut1
+ cut0
;
159 ppl_insert_dimensions_pointset (res
, 0, nb0
);
160 ppl_insert_dimensions_pointset (res
, nb0
+ cut0
, nb1
);
161 ppl_insert_dimensions_pointset (res
, nb0
+ nb1
+ cut1
,
162 dim
- nb0
- nb1
- pdim
);
167 /* Builds a constraints of the form "POS1 - POS2 CSTR_TYPE C" */
169 static ppl_Constraint_t
170 build_pairwise_constraint (graphite_dim_t dim
,
171 graphite_dim_t pos1
, graphite_dim_t pos2
,
172 int c
, enum ppl_enum_Constraint_Type cstr_type
)
174 ppl_Linear_Expression_t expr
;
175 ppl_Constraint_t cstr
;
176 ppl_Coefficient_t coef
;
184 value_set_si (v_op
, -1);
185 value_set_si (v_c
, c
);
187 ppl_new_Coefficient (&coef
);
188 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
190 ppl_assign_Coefficient_from_mpz_t (coef
, v
);
191 ppl_Linear_Expression_add_to_coefficient (expr
, pos1
, coef
);
192 ppl_assign_Coefficient_from_mpz_t (coef
, v_op
);
193 ppl_Linear_Expression_add_to_coefficient (expr
, pos2
, coef
);
194 ppl_assign_Coefficient_from_mpz_t (coef
, v_c
);
195 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
197 ppl_new_Constraint (&cstr
, expr
, cstr_type
);
199 ppl_delete_Linear_Expression (expr
);
200 ppl_delete_Coefficient (coef
);
208 /* Builds subscript equality constraints. */
210 static ppl_Pointset_Powerset_C_Polyhedron_t
211 dr_equality_constraints (graphite_dim_t dim
,
212 graphite_dim_t pos
, graphite_dim_t nb_subscripts
)
214 ppl_Polyhedron_t subscript_equalities
;
215 ppl_Pointset_Powerset_C_Polyhedron_t res
;
222 value_set_si (v_op
, -1);
224 ppl_new_C_Polyhedron_from_space_dimension (&subscript_equalities
, dim
, 0);
225 for (i
= 0; i
< nb_subscripts
; i
++)
227 ppl_Linear_Expression_t expr
;
228 ppl_Constraint_t cstr
;
229 ppl_Coefficient_t coef
;
231 ppl_new_Coefficient (&coef
);
232 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
234 ppl_assign_Coefficient_from_mpz_t (coef
, v
);
235 ppl_Linear_Expression_add_to_coefficient (expr
, pos
+ i
, coef
);
236 ppl_assign_Coefficient_from_mpz_t (coef
, v_op
);
237 ppl_Linear_Expression_add_to_coefficient (expr
, pos
+ i
+ nb_subscripts
,
240 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
241 ppl_Polyhedron_add_constraint (subscript_equalities
, cstr
);
243 ppl_delete_Linear_Expression (expr
);
244 ppl_delete_Constraint (cstr
);
245 ppl_delete_Coefficient (coef
);
248 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
249 (&res
, subscript_equalities
);
252 ppl_delete_Polyhedron (subscript_equalities
);
257 /* Builds scheduling equality constraints. */
259 static ppl_Pointset_Powerset_C_Polyhedron_t
260 build_pairwise_scheduling_equality (graphite_dim_t dim
,
261 graphite_dim_t pos
, graphite_dim_t offset
)
263 ppl_Pointset_Powerset_C_Polyhedron_t res
;
264 ppl_Polyhedron_t equalities
;
265 ppl_Constraint_t cstr
;
267 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
269 cstr
= build_pairwise_constraint (dim
, pos
, pos
+ offset
, 0,
270 PPL_CONSTRAINT_TYPE_EQUAL
);
271 ppl_Polyhedron_add_constraint (equalities
, cstr
);
272 ppl_delete_Constraint (cstr
);
274 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
275 ppl_delete_Polyhedron (equalities
);
279 /* Builds scheduling inequality constraints. */
281 static ppl_Pointset_Powerset_C_Polyhedron_t
282 build_pairwise_scheduling_inequality (graphite_dim_t dim
,
284 graphite_dim_t offset
,
287 ppl_Pointset_Powerset_C_Polyhedron_t res
;
288 ppl_Polyhedron_t equalities
;
289 ppl_Constraint_t cstr
;
291 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
294 cstr
= build_pairwise_constraint (dim
, pos
, pos
+ offset
, -1,
295 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
297 cstr
= build_pairwise_constraint (dim
, pos
, pos
+ offset
, 1,
298 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
300 ppl_Polyhedron_add_constraint (equalities
, cstr
);
301 ppl_delete_Constraint (cstr
);
303 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
304 ppl_delete_Polyhedron (equalities
);
308 /* Returns true when adding the lexicographical constraints at level I
309 to the RES dependence polyhedron returns an empty polyhedron. */
312 lexicographically_gt_p (ppl_Pointset_Powerset_C_Polyhedron_t res
,
314 graphite_dim_t offset
,
315 bool direction
, graphite_dim_t i
)
317 ppl_Pointset_Powerset_C_Polyhedron_t ineq
;
320 ineq
= build_pairwise_scheduling_inequality (dim
, i
, offset
,
322 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq
, res
);
323 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq
);
325 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, ineq
);
326 ppl_delete_Pointset_Powerset_C_Polyhedron (ineq
);
331 /* Build the precedence constraints for the lexicographical comparison
332 of time vectors RES following the lexicographical order. */
335 build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t
*res
,
337 graphite_dim_t tdim1
,
338 graphite_dim_t offset
,
343 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, 0))
346 for (i
= 0; i
< tdim1
- 1; i
++)
348 ppl_Pointset_Powerset_C_Polyhedron_t sceq
;
350 sceq
= build_pairwise_scheduling_equality (dim
, i
, offset
);
351 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res
, sceq
);
352 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq
);
354 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, i
+ 1))
360 ppl_delete_Pointset_Powerset_C_Polyhedron (*res
);
361 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res
, dim
, 1);
365 /* Build the dependence polyhedron for data references PDR1 and PDR2. */
367 static ppl_Pointset_Powerset_C_Polyhedron_t
368 dependence_polyhedron_1 (poly_bb_p pbb1
, poly_bb_p pbb2
,
369 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
370 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
371 poly_dr_p pdr1
, poly_dr_p pdr2
,
372 ppl_Polyhedron_t s1
, ppl_Polyhedron_t s2
,
374 bool original_scattering_p
)
376 scop_p scop
= PBB_SCOP (pbb1
);
377 graphite_dim_t tdim1
= original_scattering_p
?
378 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
379 graphite_dim_t tdim2
= original_scattering_p
?
380 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
381 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
382 graphite_dim_t ddim2
= pbb_dim_iter_domain (pbb2
);
383 graphite_dim_t sdim1
= pdr_nb_subscripts (pdr1
) + 1;
384 graphite_dim_t gdim
= scop_nb_params (scop
);
385 graphite_dim_t dim1
= pdr_dim (pdr1
);
386 graphite_dim_t dim2
= pdr_dim (pdr2
);
387 graphite_dim_t dim
= tdim1
+ tdim2
+ dim1
+ dim2
;
388 ppl_Pointset_Powerset_C_Polyhedron_t res
;
389 ppl_Pointset_Powerset_C_Polyhedron_t id1
, id2
, isc1
, isc2
, idr1
, idr2
;
390 ppl_Pointset_Powerset_C_Polyhedron_t sc1
, sc2
, dreq
;
392 gcc_assert (PBB_SCOP (pbb1
) == PBB_SCOP (pbb2
));
393 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1
, s1
);
394 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2
, s2
);
396 id1
= map_into_dep_poly (dim
, gdim
, d1
, ddim1
, tdim1
);
397 id2
= map_into_dep_poly (dim
, gdim
, d2
, ddim2
, tdim1
+ ddim1
+ tdim2
);
398 isc1
= map_into_dep_poly (dim
, gdim
, sc1
, ddim1
+ tdim1
, 0);
399 isc2
= map_into_dep_poly (dim
, gdim
, sc2
, ddim2
+ tdim2
, tdim1
+ ddim1
);
401 idr1
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr1
), ddim1
, ddim1
+ gdim
,
402 tdim1
, tdim2
+ ddim2
);
403 idr2
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr2
), ddim2
, ddim2
+ gdim
,
404 tdim1
+ ddim1
+ tdim2
, sdim1
);
406 /* Now add the subscript equalities. */
407 dreq
= dr_equality_constraints (dim
, tdim1
+ ddim1
+ tdim2
+ ddim2
, sdim1
);
409 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 0);
410 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id1
);
411 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id2
);
412 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc1
);
413 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc2
);
414 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr1
);
415 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr2
);
416 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, dreq
);
417 ppl_delete_Pointset_Powerset_C_Polyhedron (id1
);
418 ppl_delete_Pointset_Powerset_C_Polyhedron (id2
);
419 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1
);
420 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2
);
421 ppl_delete_Pointset_Powerset_C_Polyhedron (isc1
);
422 ppl_delete_Pointset_Powerset_C_Polyhedron (isc2
);
423 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1
);
424 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2
);
425 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq
);
427 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res
))
428 build_lexicographically_gt_constraint (&res
, dim
, MIN (tdim1
, tdim2
),
429 tdim1
+ ddim1
, direction
);
433 /* Build the dependence polyhedron for data references PDR1 and PDR2.
434 If possible use already cached information. */
436 static ppl_Pointset_Powerset_C_Polyhedron_t
437 dependence_polyhedron (poly_bb_p pbb1
, poly_bb_p pbb2
,
438 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
439 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
440 poly_dr_p pdr1
, poly_dr_p pdr2
,
441 ppl_Polyhedron_t s1
, ppl_Polyhedron_t s2
,
443 bool original_scattering_p
)
447 ppl_Pointset_Powerset_C_Polyhedron_t res
;
449 if (original_scattering_p
)
453 x
= htab_find_slot (SCOP_ORIGINAL_PDR_PAIRS (PBB_SCOP (pbb1
)),
458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
459 fprintf (dump_file
, "\nddp cache: hit.\n");
460 return ((poly_dr_pair
*)*x
)->ddp
;
462 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
463 fprintf (dump_file
, "\nddp cache: miss.\n");
466 res
= dependence_polyhedron_1 (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
,
467 s1
, s2
, direction
, original_scattering_p
);
469 if (original_scattering_p
)
471 gcc_assert (x
&& *x
== NULL
);
472 *x
= new_poly_dr_pair (pdr1
, pdr2
, res
);
474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
475 fprintf (dump_file
, "\nddp cache: add element.\n");
481 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
482 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
486 graphite_legal_transform_dr (poly_bb_p pbb1
, poly_bb_p pbb2
,
487 poly_dr_p pdr1
, poly_dr_p pdr2
)
489 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
490 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
491 ppl_Polyhedron_t so1
= PBB_ORIGINAL_SCATTERING (pbb1
);
492 ppl_Polyhedron_t so2
= PBB_ORIGINAL_SCATTERING (pbb2
);
493 ppl_Pointset_Powerset_C_Polyhedron_t po
;
495 graphite_dim_t sdim1
= pdr_nb_subscripts (pdr1
) + 1;
496 graphite_dim_t sdim2
= pdr_nb_subscripts (pdr2
) + 1;
501 po
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, so1
, so2
,
504 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (po
))
508 ppl_Polyhedron_t st1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
509 ppl_Polyhedron_t st2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
510 ppl_Pointset_Powerset_C_Polyhedron_t pt
;
511 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
512 graphite_dim_t otdim1
= pbb_nb_scattering_orig (pbb1
);
513 graphite_dim_t otdim2
= pbb_nb_scattering_orig (pbb2
);
514 graphite_dim_t ttdim1
= pbb_nb_scattering_transform (pbb1
);
515 graphite_dim_t ttdim2
= pbb_nb_scattering_transform (pbb2
);
517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
518 fprintf (dump_file
, "\nloop carries dependency.\n");
519 pt
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, st1
, st2
,
522 /* Extend PO and PT to have the same dimensions. */
523 ppl_insert_dimensions_pointset (po
, otdim1
, ttdim1
);
524 ppl_insert_dimensions_pointset (po
, otdim1
+ ttdim1
+ ddim1
+ otdim2
,
526 ppl_insert_dimensions_pointset (pt
, 0, otdim1
);
527 ppl_insert_dimensions_pointset (pt
, otdim1
+ ttdim1
+ ddim1
, otdim2
);
529 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po
, pt
);
530 return ppl_Pointset_Powerset_C_Polyhedron_is_empty (po
);
534 /* Iterates over the data references of PBB1 and PBB2 and detect
535 whether the transformed schedule is correct. */
538 graphite_legal_transform_bb (poly_bb_p pbb1
, poly_bb_p pbb2
)
541 poly_dr_p pdr1
, pdr2
;
543 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
544 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
545 if (!graphite_legal_transform_dr (pbb1
, pbb2
, pdr1
, pdr2
))
550 /* Iterates over the SCOP and detect whether the transformed schedule
554 graphite_legal_transform (scop_p scop
)
557 poly_bb_p pbb1
, pbb2
;
559 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
560 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
561 if (!graphite_legal_transform_bb (pbb1
, pbb2
))
567 /* Remove all the dimensions except alias information at dimension
571 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset
,
572 ppl_dimension_type alias_dim
)
574 ppl_dimension_type
*ds
;
575 ppl_dimension_type access_dim
;
578 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset
,
580 ds
= XNEWVEC (ppl_dimension_type
, access_dim
-1);
581 for (i
= 0; i
< access_dim
; i
++)
590 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset
,
596 /* Return true when PDR1 and PDR2 may alias. */
599 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
601 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1
, alias_powerset2
;
602 ppl_Pointset_Powerset_C_Polyhedron_t accesses1
= PDR_ACCESSES (pdr1
);
603 ppl_Pointset_Powerset_C_Polyhedron_t accesses2
= PDR_ACCESSES (pdr2
);
604 ppl_dimension_type alias_dim1
= pdr_alias_set_dim (pdr1
);
605 ppl_dimension_type alias_dim2
= pdr_alias_set_dim (pdr2
);
608 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
609 (&alias_powerset1
, accesses1
);
610 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
611 (&alias_powerset2
, accesses2
);
613 build_alias_set_powerset (alias_powerset1
, alias_dim1
);
614 build_alias_set_powerset (alias_powerset2
, alias_dim2
);
616 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
617 (alias_powerset1
, alias_powerset2
);
619 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1
);
621 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1
);
622 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2
);
627 /* Returns TRUE when the dependence polyhedron between PDR1 and
628 PDR2 represents a loop carried dependence at level LEVEL. Otherwise
632 graphite_carried_dependence_level_k (poly_dr_p pdr1
, poly_dr_p pdr2
,
635 poly_bb_p pbb1
= PDR_PBB (pdr1
);
636 poly_bb_p pbb2
= PDR_PBB (pdr2
);
637 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
638 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
639 ppl_Polyhedron_t so1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
640 ppl_Polyhedron_t so2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
641 ppl_Pointset_Powerset_C_Polyhedron_t po
;
642 ppl_Pointset_Powerset_C_Polyhedron_t eqpp
;
643 graphite_dim_t sdim1
= pdr_nb_subscripts (pdr1
) + 1;
644 graphite_dim_t sdim2
= pdr_nb_subscripts (pdr2
) + 1;
645 graphite_dim_t tdim1
= pbb_nb_scattering_transform (pbb1
);
646 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
647 ppl_dimension_type dim
;
650 if ((PDR_TYPE (pdr1
) == PDR_READ
&& PDR_TYPE (pdr2
) == PDR_READ
)
651 || !poly_drs_may_alias_p (pdr1
, pdr2
))
657 po
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, so1
, so2
,
659 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (po
))
661 ppl_delete_Pointset_Powerset_C_Polyhedron (po
);
665 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &dim
);
666 eqpp
= build_pairwise_scheduling_inequality (dim
, level
, tdim1
+ ddim1
, 1);
668 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp
, po
);
669 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp
);
671 ppl_delete_Pointset_Powerset_C_Polyhedron (po
);
672 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp
);
676 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
679 dependency_between_pbbs_p (poly_bb_p pbb1
, poly_bb_p pbb2
, int level
)
682 poly_dr_p pdr1
, pdr2
;
684 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
685 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
686 if (graphite_carried_dependence_level_k (pdr1
, pdr2
, level
))