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 timevar_push (TV_GRAPHITE_DATA_DEPS);
561 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
562 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
563 if (!graphite_legal_transform_bb (pbb1, pbb2))
565 timevar_pop (TV_GRAPHITE_DATA_DEPS);
569 timevar_pop (TV_GRAPHITE_DATA_DEPS);
573 /* Remove all the dimensions except alias information at dimension
577 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
578 ppl_dimension_type alias_dim)
580 ppl_dimension_type *ds;
581 ppl_dimension_type access_dim;
584 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
586 ds = XNEWVEC (ppl_dimension_type, access_dim-1);
587 for (i = 0; i < access_dim; i++)
596 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
602 /* Return true when PDR1 and PDR2 may alias. */
605 poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
607 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
608 ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
609 ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
610 ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
611 ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
614 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
615 (&alias_powerset1, accesses1);
616 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
617 (&alias_powerset2, accesses2);
619 build_alias_set_powerset (alias_powerset1, alias_dim1);
620 build_alias_set_powerset (alias_powerset2, alias_dim2);
622 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
623 (alias_powerset1, alias_powerset2);
625 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
627 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
628 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
633 /* Returns TRUE when the dependence polyhedron between PDR1 and
634 PDR2 represents a loop carried dependence at level LEVEL. Otherwise
638 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
641 poly_bb_p pbb1 = PDR_PBB (pdr1);
642 poly_bb_p pbb2 = PDR_PBB (pdr2);
643 ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
644 ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
645 ppl_Polyhedron_t so1 = PBB_TRANSFORMED_SCATTERING (pbb1);
646 ppl_Polyhedron_t so2 = PBB_TRANSFORMED_SCATTERING (pbb2);
647 ppl_Pointset_Powerset_C_Polyhedron_t po;
648 ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
649 graphite_dim_t sdim1 = pdr_nb_subscripts (pdr1) + 1;
650 graphite_dim_t sdim2 = pdr_nb_subscripts (pdr2) + 1;
651 graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
652 graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
653 ppl_dimension_type dim;
656 if ((PDR_TYPE (pdr1) == PDR_READ && PDR_TYPE (pdr2) == PDR_READ)
657 || !poly_drs_may_alias_p (pdr1, pdr2))
663 po = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
665 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (po))
667 ppl_delete_Pointset_Powerset_C_Polyhedron (po);
671 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
672 eqpp = build_pairwise_scheduling_inequality (dim, level, tdim1 + ddim1, 1);
674 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
675 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
677 ppl_delete_Pointset_Powerset_C_Polyhedron (po);
678 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
682 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
685 dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
688 poly_dr_p pdr1, pdr2;
690 timevar_push (TV_GRAPHITE_DATA_DEPS);
692 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
693 for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
694 if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
696 timevar_pop (TV_GRAPHITE_DATA_DEPS);
700 timevar_pop (TV_GRAPHITE_DATA_DEPS);