1 /* Graphite polyhedral representation.
2 Copyright (C) 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
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/>. */
23 #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 "value-prof.h"
42 #include "pointer-set.h"
47 #include "cloog/cloog.h"
50 #include "graphite-ppl.h"
52 #include "graphite-poly.h"
53 #include "graphite-dependences.h"
55 /* Return the maximal loop depth in SCOP. */
58 scop_max_loop_depth (scop_p scop)
64 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
66 int nb_loops = pbb_dim_iter_domain (pbb);
67 if (max_nb_loops < nb_loops)
68 max_nb_loops = nb_loops;
74 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
78 extend_scattering (poly_bb_p pbb, int max_scattering)
80 ppl_dimension_type nb_old_dims, nb_new_dims;
82 ppl_Coefficient_t coef;
85 nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb);
87 value_set_si (one, 1);
88 ppl_new_Coefficient (&coef);
89 ppl_assign_Coefficient_from_mpz_t (coef, one);
91 gcc_assert (nb_added_dims >= 0);
93 nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb)
94 + scop_nb_params (PBB_SCOP (pbb));
95 nb_new_dims = nb_old_dims + nb_added_dims;
97 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb),
98 pbb_nb_scattering_transform (pbb), nb_added_dims);
99 PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims;
101 /* Add identity matrix for the added dimensions. */
102 for (i = max_scattering - nb_added_dims; i < max_scattering; i++)
104 ppl_Constraint_t cstr;
105 ppl_Linear_Expression_t expr;
107 ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims);
108 ppl_Linear_Expression_add_to_coefficient (expr, i, coef);
109 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
110 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
111 ppl_delete_Constraint (cstr);
112 ppl_delete_Linear_Expression (expr);
115 ppl_delete_Coefficient (coef);
119 /* All scattering matrices in SCOP will have the same number of scattering
123 unify_scattering_dimensions (scop_p scop)
127 graphite_dim_t max_scattering = 0;
129 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
130 max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering);
132 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
133 extend_scattering (pbb, max_scattering);
135 return max_scattering;
138 /* Prints to FILE the scattering function of PBB. */
141 print_scattering_function (FILE *file, poly_bb_p pbb)
145 if (!PBB_TRANSFORMED (pbb))
148 fprintf (file, "scattering bb_%d (\n", GBB_BB (PBB_BLACK_BOX (pbb))->index);
149 fprintf (file, "# eq");
151 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
152 fprintf (file, " s%d", (int) i);
154 for (i = 0; i < pbb_nb_local_vars (pbb); i++)
155 fprintf (file, " lv%d", (int) i);
157 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
158 fprintf (file, " i%d", (int) i);
160 for (i = 0; i < pbb_nb_params (pbb); i++)
161 fprintf (file, " p%d", (int) i);
163 fprintf (file, " cst\n");
165 ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb));
167 fprintf (file, ")\n");
170 /* Prints to FILE the iteration domain of PBB. */
173 print_iteration_domain (FILE *file, poly_bb_p pbb)
175 print_pbb_domain (file, pbb);
178 /* Prints to FILE the scattering functions of every PBB of SCOP. */
181 print_scattering_functions (FILE *file, scop_p scop)
186 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
187 print_scattering_function (file, pbb);
190 /* Prints to FILE the iteration domains of every PBB of SCOP. */
193 print_iteration_domains (FILE *file, scop_p scop)
198 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
199 print_iteration_domain (file, pbb);
202 /* Prints to STDERR the scattering function of PBB. */
205 debug_scattering_function (poly_bb_p pbb)
207 print_scattering_function (stderr, pbb);
210 /* Prints to STDERR the iteration domain of PBB. */
213 debug_iteration_domain (poly_bb_p pbb)
215 print_iteration_domain (stderr, pbb);
218 /* Prints to STDERR the scattering functions of every PBB of SCOP. */
221 debug_scattering_functions (scop_p scop)
223 print_scattering_functions (stderr, scop);
226 /* Prints to STDERR the iteration domains of every PBB of SCOP. */
229 debug_iteration_domains (scop_p scop)
231 print_iteration_domains (stderr, scop);
234 /* Apply graphite transformations to all the basic blocks of SCOP. */
237 apply_poly_transforms (scop_p scop)
239 bool transform_done = false;
241 gcc_assert (graphite_legal_transform (scop));
243 /* Generate code even if we did not apply any real transformation.
244 This also allows to check the performance for the identity
245 transformation: GIMPLE -> GRAPHITE -> GIMPLE
246 Keep in mind that CLooG optimizes in control, so the loop structure
247 may change, even if we only use -fgraphite-identity. */
248 if (flag_graphite_identity)
249 transform_done = true;
251 if (flag_loop_parallelize_all)
252 transform_done = true;
255 gcc_unreachable (); /* Not yet supported. */
257 if (flag_loop_strip_mine)
258 transform_done |= scop_do_strip_mine (scop);
260 if (flag_loop_interchange)
261 transform_done |= scop_do_interchange (scop);
263 return transform_done;
266 /* Create a new polyhedral data reference and add it to PBB. It is defined by
267 its ACCESSES, its TYPE*/
270 new_poly_dr (poly_bb_p pbb,
271 ppl_Pointset_Powerset_C_Polyhedron_t accesses,
272 enum POLY_DR_TYPE type, void *cdr)
274 poly_dr_p pdr = XNEW (struct poly_dr);
277 PDR_ACCESSES (pdr) = accesses;
278 PDR_TYPE (pdr) = type;
280 VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
283 /* Free polyhedral data reference PDR. */
286 free_poly_dr (poly_dr_p pdr)
288 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
292 /* Create a new polyhedral black box. */
295 new_poly_bb (scop_p scop, void *black_box)
297 poly_bb_p pbb = XNEW (struct poly_bb);
299 PBB_DOMAIN (pbb) = NULL;
300 PBB_SCOP (pbb) = scop;
301 pbb_set_black_box (pbb, black_box);
302 PBB_TRANSFORMED (pbb) = NULL;
303 PBB_SAVED (pbb) = NULL;
304 PBB_ORIGINAL (pbb) = NULL;
305 PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
306 VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
309 /* Free polyhedral black box. */
312 free_poly_bb (poly_bb_p pbb)
317 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
319 if (PBB_TRANSFORMED (pbb))
320 poly_scattering_free (PBB_TRANSFORMED (pbb));
323 poly_scattering_free (PBB_SAVED (pbb));
325 if (PBB_ORIGINAL (pbb))
326 poly_scattering_free (PBB_ORIGINAL (pbb));
329 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
332 VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
337 print_pdr_access_layout (FILE *file, poly_dr_p pdr)
341 fprintf (file, "# eq");
343 for (i = 0; i < pdr_dim_iter_domain (pdr); i++)
344 fprintf (file, " i%d", (int) i);
346 for (i = 0; i < pdr_nb_params (pdr); i++)
347 fprintf (file, " p%d", (int) i);
349 fprintf (file, " alias");
351 for (i = 0; i < pdr_nb_subscripts (pdr); i++)
352 fprintf (file, " sub%d", (int) i);
354 fprintf (file, " cst\n");
357 /* Prints to FILE the polyhedral data reference PDR. */
360 print_pdr (FILE *file, poly_dr_p pdr)
362 fprintf (file, "pdr (");
364 switch (PDR_TYPE (pdr))
367 fprintf (file, "read \n");
371 fprintf (file, "write \n");
375 fprintf (file, "may_write \n");
382 dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
384 fprintf (file, "data accesses (\n");
385 print_pdr_access_layout (file, pdr);
386 ppl_print_powerset_matrix (file, PDR_ACCESSES (pdr));
387 fprintf (file, ")\n");
389 fprintf (file, ")\n");
392 /* Prints to STDERR the polyhedral data reference PDR. */
395 debug_pdr (poly_dr_p pdr)
397 print_pdr (stderr, pdr);
400 /* Creates a new SCOP containing REGION. */
403 new_scop (void *region)
405 scop_p scop = XNEW (struct scop);
407 SCOP_DEP_GRAPH (scop) = NULL;
408 SCOP_CONTEXT (scop) = NULL;
409 scop_set_region (scop, region);
410 SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
411 SCOP_ORIGINAL_PDR_PAIRS (scop) = htab_create (10, hash_poly_dr_pair_p,
412 eq_poly_dr_pair_p, free);
419 free_scop (scop_p scop)
424 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
427 VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
429 if (SCOP_CONTEXT (scop))
430 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
432 htab_delete (SCOP_ORIGINAL_PDR_PAIRS (scop));
436 /* Print to FILE the domain of PBB. */
439 print_pbb_domain (FILE *file, poly_bb_p pbb)
442 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
444 if (!PBB_DOMAIN (pbb))
447 fprintf (file, "domains bb_%d (\n", GBB_BB (gbb)->index);
448 fprintf (file, "# eq");
450 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
451 fprintf (file, " i%d", (int) i);
453 for (i = 0; i < pbb_nb_params (pbb); i++)
454 fprintf (file, " p%d", (int) i);
456 fprintf (file, " cst\n");
458 if (PBB_DOMAIN (pbb))
459 ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
461 fprintf (file, ")\n");
464 /* Dump the cases of a graphite basic block GBB on FILE. */
467 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
471 VEC (gimple, heap) *cases;
476 cases = GBB_CONDITION_CASES (gbb);
477 if (VEC_empty (gimple, cases))
480 fprintf (file, "cases bb_%d (", GBB_BB (gbb)->index);
482 for (i = 0; VEC_iterate (gimple, cases, i, stmt); i++)
483 print_gimple_stmt (file, stmt, 0, 0);
485 fprintf (file, ")\n");
488 /* Dump conditions of a graphite basic block GBB on FILE. */
491 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
495 VEC (gimple, heap) *conditions;
500 conditions = GBB_CONDITIONS (gbb);
501 if (VEC_empty (gimple, conditions))
504 fprintf (file, "conditions bb_%d (", GBB_BB (gbb)->index);
506 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
507 print_gimple_stmt (file, stmt, 0, 0);
509 fprintf (file, ")\n");
512 /* Print to FILE all the data references of PBB. */
515 print_pdrs (FILE *file, poly_bb_p pbb)
520 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
521 print_pdr (file, pdr);
524 /* Print to STDERR all the data references of PBB. */
527 debug_pdrs (poly_bb_p pbb)
529 print_pdrs (stderr, pbb);
532 /* Print to FILE the domain and scattering function of PBB. */
535 print_pbb (FILE *file, poly_bb_p pbb)
537 fprintf (file, "pbb (\n");
538 dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
539 dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
540 print_pdrs (file, pbb);
541 print_pbb_domain (file, pbb);
542 print_scattering_function (file, pbb);
543 fprintf (file, ")\n");
546 /* Print to FILE the parameters of SCOP. */
549 print_scop_params (FILE *file, scop_p scop)
554 fprintf (file, "parameters (\n");
555 for (i = 0; VEC_iterate (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t); i++)
557 fprintf (file, "p_%d -> ", i);
558 print_generic_expr (file, t, 0);
559 fprintf (file, "\n");
561 fprintf (file, ")\n");
564 /* Print to FILE the context of SCoP. */
566 print_scop_context (FILE *file, scop_p scop)
570 fprintf (file, "context (\n");
571 fprintf (file, "# eq");
573 for (i = 0; i < scop_nb_params (scop); i++)
574 fprintf (file, " p%d", (int) i);
576 fprintf (file, " cst\n");
578 if (SCOP_CONTEXT (scop))
579 ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
581 fprintf (file, ")\n");
584 /* Print to FILE the SCOP. */
587 print_scop (FILE *file, scop_p scop)
592 fprintf (file, "scop (\n");
593 print_scop_params (file, scop);
594 print_scop_context (file, scop);
596 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
597 print_pbb (file, pbb);
599 fprintf (file, ")\n");
602 /* Print to STDERR the domain of PBB. */
605 debug_pbb_domain (poly_bb_p pbb)
607 print_pbb_domain (stderr, pbb);
610 /* Print to FILE the domain and scattering function of PBB. */
613 debug_pbb (poly_bb_p pbb)
615 print_pbb (stderr, pbb);
618 /* Print to STDERR the context of SCOP. */
621 debug_scop_context (scop_p scop)
623 print_scop_context (stderr, scop);
626 /* Print to STDERR the SCOP. */
629 debug_scop (scop_p scop)
631 print_scop (stderr, scop);
634 /* Print to STDERR the parameters of SCOP. */
637 debug_scop_params (scop_p scop)
639 print_scop_params (stderr, scop);
643 /* The dimension in the transformed scattering polyhedron of PBB
644 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
647 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
649 ppl_const_Constraint_System_t pcs;
650 ppl_Constraint_System_const_iterator_t cit, cend;
651 ppl_const_Constraint_t cstr;
652 ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
653 ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
654 ppl_Linear_Expression_t expr;
655 ppl_Coefficient_t coef;
660 ppl_new_Coefficient (&coef);
661 ppl_Polyhedron_get_constraints (ph, &pcs);
662 ppl_new_Constraint_System_const_iterator (&cit);
663 ppl_new_Constraint_System_const_iterator (&cend);
665 for (ppl_Constraint_System_begin (pcs, cit),
666 ppl_Constraint_System_end (pcs, cend);
667 !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
668 ppl_Constraint_System_const_iterator_increment (cit))
670 ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
671 ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
672 ppl_Linear_Expression_coefficient (expr, iter, coef);
673 ppl_Coefficient_to_mpz_t (coef, val);
675 if (value_zero_p (val))
677 ppl_delete_Linear_Expression (expr);
681 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
683 ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
685 ppl_Linear_Expression_coefficient (expr, scatter, coef);
686 ppl_Coefficient_to_mpz_t (coef, val);
688 if (value_notzero_p (val))
691 ppl_delete_Linear_Expression (expr);
692 ppl_delete_Coefficient (coef);
693 ppl_delete_Constraint_System_const_iterator (cit);
694 ppl_delete_Constraint_System_const_iterator (cend);
704 /* Returns the number of iterations NITER of the loop around PBB at
708 pbb_number_of_iterations (poly_bb_p pbb,
709 graphite_dim_t loop_depth,
712 ppl_dimension_type loop_iter = pbb_iterator_dim (pbb, loop_depth);
713 ppl_Linear_Expression_t le;
714 ppl_Coefficient_t num, denom;
717 ppl_dimension_type dim;
720 ppl_new_Coefficient (&num);
721 ppl_new_Coefficient (&denom);
722 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
723 ppl_new_Linear_Expression_with_dimension (&le, dim);
724 ppl_set_coef (le, loop_iter, 1);
725 ppl_Pointset_Powerset_C_Polyhedron_maximize (PBB_DOMAIN (pbb), le,
726 num, denom, &maximum);
730 ppl_Coefficient_to_mpz_t (num, niter);
731 ppl_Coefficient_to_mpz_t (denom, dv);
732 value_division (niter, niter, dv);
735 value_set_si (niter, -1);
738 ppl_delete_Linear_Expression (le);
739 ppl_delete_Coefficient (num);
740 ppl_delete_Coefficient (denom);