1 /* Graphite polyhedral representation.
2 Copyright (C) 2009, 2010 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-pretty-print.h"
32 #include "gimple-pretty-print.h"
33 #include "tree-flow.h"
35 #include "tree-dump.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
49 #include "cloog/cloog.h"
52 #include "graphite-ppl.h"
54 #include "graphite-poly.h"
55 #include "graphite-dependences.h"
57 /* Return the maximal loop depth in SCOP. */
60 scop_max_loop_depth (scop_p scop
)
66 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
68 int nb_loops
= pbb_dim_iter_domain (pbb
);
69 if (max_nb_loops
< nb_loops
)
70 max_nb_loops
= nb_loops
;
76 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
80 extend_scattering (poly_bb_p pbb
, int max_scattering
)
82 ppl_dimension_type nb_old_dims
, nb_new_dims
;
84 ppl_Coefficient_t coef
;
87 nb_added_dims
= max_scattering
- pbb_nb_scattering_transform (pbb
);
90 ppl_new_Coefficient (&coef
);
91 ppl_assign_Coefficient_from_mpz_t (coef
, one
);
93 gcc_assert (nb_added_dims
>= 0);
95 nb_old_dims
= pbb_nb_scattering_transform (pbb
) + pbb_dim_iter_domain (pbb
)
96 + scop_nb_params (PBB_SCOP (pbb
));
97 nb_new_dims
= nb_old_dims
+ nb_added_dims
;
99 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
),
100 pbb_nb_scattering_transform (pbb
), nb_added_dims
);
101 PBB_NB_SCATTERING_TRANSFORM (pbb
) += nb_added_dims
;
103 /* Add identity matrix for the added dimensions. */
104 for (i
= max_scattering
- nb_added_dims
; i
< max_scattering
; i
++)
106 ppl_Constraint_t cstr
;
107 ppl_Linear_Expression_t expr
;
109 ppl_new_Linear_Expression_with_dimension (&expr
, nb_new_dims
);
110 ppl_Linear_Expression_add_to_coefficient (expr
, i
, coef
);
111 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
112 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
113 ppl_delete_Constraint (cstr
);
114 ppl_delete_Linear_Expression (expr
);
117 ppl_delete_Coefficient (coef
);
121 /* All scattering matrices in SCOP will have the same number of scattering
125 unify_scattering_dimensions (scop_p scop
)
129 graphite_dim_t max_scattering
= 0;
131 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
132 max_scattering
= MAX (pbb_nb_scattering_transform (pbb
), max_scattering
);
134 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
135 extend_scattering (pbb
, max_scattering
);
137 return max_scattering
;
140 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
144 print_scattering_function_1 (FILE *file
, poly_bb_p pbb
, int verbosity
)
150 fprintf (file
, "# scattering bb_%d (\n", pbb_index (pbb
));
151 fprintf (file
, "# eq");
153 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
154 fprintf (file
, " s%d", (int) i
);
156 for (i
= 0; i
< pbb_nb_local_vars (pbb
); i
++)
157 fprintf (file
, " lv%d", (int) i
);
159 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
160 fprintf (file
, " i%d", (int) i
);
162 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
163 fprintf (file
, " p%d", (int) i
);
165 fprintf (file
, " cst\n");
168 /* Number of disjunct components. Remove this when
169 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
170 fprintf (file
, "1\n");
171 ppl_print_polyhedron_matrix (file
, PBB_TRANSFORMED_SCATTERING (pbb
)
172 ? PBB_TRANSFORMED_SCATTERING (pbb
)
173 : PBB_ORIGINAL_SCATTERING (pbb
));
176 fprintf (file
, "#)\n");
179 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
183 print_scattering_function (FILE *file
, poly_bb_p pbb
, int verbosity
)
185 if (!PBB_TRANSFORMED (pbb
))
188 if (PBB_TRANSFORMED_SCATTERING (pbb
)
189 || PBB_ORIGINAL_SCATTERING (pbb
))
192 fprintf (file
, "# Scattering function is provided\n");
194 fprintf (file
, "1\n");
199 fprintf (file
, "# Scattering function is not provided\n");
201 fprintf (file
, "0\n");
205 print_scattering_function_1 (file
, pbb
, verbosity
);
208 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
212 print_iteration_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
214 print_pbb_domain (file
, pbb
, verbosity
);
217 /* Prints to FILE the scattering functions of every PBB of SCOP. */
220 print_scattering_functions (FILE *file
, scop_p scop
, int verbosity
)
225 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
226 print_scattering_function (file
, pbb
, verbosity
);
229 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
233 print_iteration_domains (FILE *file
, scop_p scop
, int verbosity
)
238 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
239 print_iteration_domain (file
, pbb
, verbosity
);
242 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
246 debug_scattering_function (poly_bb_p pbb
, int verbosity
)
248 print_scattering_function (stderr
, pbb
, verbosity
);
251 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
255 debug_iteration_domain (poly_bb_p pbb
, int verbosity
)
257 print_iteration_domain (stderr
, pbb
, verbosity
);
260 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
261 some VERBOSITY level. */
264 debug_scattering_functions (scop_p scop
, int verbosity
)
266 print_scattering_functions (stderr
, scop
, verbosity
);
269 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
270 some VERBOSITY level. */
273 debug_iteration_domains (scop_p scop
, int verbosity
)
275 print_iteration_domains (stderr
, scop
, verbosity
);
279 /* Apply graphite transformations to all the basic blocks of SCOP. */
282 apply_poly_transforms (scop_p scop
)
284 bool transform_done
= false;
286 /* Generate code even if we did not apply any real transformation.
287 This also allows to check the performance for the identity
288 transformation: GIMPLE -> GRAPHITE -> GIMPLE
289 Keep in mind that CLooG optimizes in control, so the loop structure
290 may change, even if we only use -fgraphite-identity. */
291 if (flag_graphite_identity
)
292 transform_done
= true;
294 if (flag_loop_parallelize_all
)
295 transform_done
= true;
298 transform_done
|= scop_do_block (scop
);
301 if (flag_loop_strip_mine
)
302 transform_done
|= scop_do_strip_mine (scop
);
304 if (flag_loop_interchange
)
305 transform_done
|= scop_do_interchange (scop
);
308 return transform_done
;
311 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
312 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */
315 can_collapse_pdrs (poly_dr_p pdr1
, poly_dr_p pdr2
)
318 ppl_Pointset_Powerset_C_Polyhedron_t af1
, af2
, diff
;
320 if (PDR_PBB (pdr1
) != PDR_PBB (pdr2
)
321 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
)
322 || PDR_TYPE (pdr1
) != PDR_TYPE (pdr2
))
325 af1
= PDR_ACCESSES (pdr1
);
326 af2
= PDR_ACCESSES (pdr2
);
327 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
329 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff
, af2
);
331 res
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff
);
332 ppl_delete_Pointset_Powerset_C_Polyhedron (diff
);
336 /* Removes duplicated data references in PBB. */
339 pbb_remove_duplicate_pdrs (poly_bb_p pbb
)
342 poly_dr_p pdr1
, pdr2
;
343 unsigned n
= VEC_length (poly_dr_p
, PBB_DRS (pbb
));
344 VEC (poly_dr_p
, heap
) *collapsed
= VEC_alloc (poly_dr_p
, heap
, n
);
346 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr1
); i
++)
347 for (j
= 0; VEC_iterate (poly_dr_p
, collapsed
, j
, pdr2
); j
++)
348 if (!can_collapse_pdrs (pdr1
, pdr2
))
349 VEC_quick_push (poly_dr_p
, collapsed
, pdr1
);
351 VEC_free (poly_dr_p
, heap
, collapsed
);
352 PBB_PDR_DUPLICATES_REMOVED (pbb
) = true;
355 /* Create a new polyhedral data reference and add it to PBB. It is
356 defined by its ACCESSES, its TYPE, and the number of subscripts
360 new_poly_dr (poly_bb_p pbb
, int dr_base_object_set
,
361 ppl_Pointset_Powerset_C_Polyhedron_t accesses
,
362 enum poly_dr_type type
, void *cdr
, graphite_dim_t nb_subscripts
)
365 poly_dr_p pdr
= XNEW (struct poly_dr
);
368 PDR_BASE_OBJECT_SET (pdr
) = dr_base_object_set
;
369 PDR_NB_REFS (pdr
) = 1;
371 PDR_ACCESSES (pdr
) = accesses
;
372 PDR_TYPE (pdr
) = type
;
374 PDR_NB_SUBSCRIPTS (pdr
) = nb_subscripts
;
375 VEC_safe_push (poly_dr_p
, heap
, PBB_DRS (pbb
), pdr
);
378 /* Free polyhedral data reference PDR. */
381 free_poly_dr (poly_dr_p pdr
)
383 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr
));
387 /* Create a new polyhedral black box. */
390 new_poly_bb (scop_p scop
, void *black_box
, bool reduction
)
392 poly_bb_p pbb
= XNEW (struct poly_bb
);
394 PBB_DOMAIN (pbb
) = NULL
;
395 PBB_SCOP (pbb
) = scop
;
396 pbb_set_black_box (pbb
, black_box
);
397 PBB_TRANSFORMED (pbb
) = NULL
;
398 PBB_SAVED (pbb
) = NULL
;
399 PBB_ORIGINAL (pbb
) = NULL
;
400 PBB_DRS (pbb
) = VEC_alloc (poly_dr_p
, heap
, 3);
401 PBB_IS_REDUCTION (pbb
) = reduction
;
402 PBB_PDR_DUPLICATES_REMOVED (pbb
) = false;
403 VEC_safe_push (poly_bb_p
, heap
, SCOP_BBS (scop
), pbb
);
406 /* Free polyhedral black box. */
409 free_poly_bb (poly_bb_p pbb
)
414 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb
));
416 if (PBB_TRANSFORMED (pbb
))
417 poly_scattering_free (PBB_TRANSFORMED (pbb
));
420 poly_scattering_free (PBB_SAVED (pbb
));
422 if (PBB_ORIGINAL (pbb
))
423 poly_scattering_free (PBB_ORIGINAL (pbb
));
426 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
429 VEC_free (poly_dr_p
, heap
, PBB_DRS (pbb
));
434 print_pdr_access_layout (FILE *file
, poly_dr_p pdr
)
438 fprintf (file
, "# eq");
440 for (i
= 0; i
< pdr_dim_iter_domain (pdr
); i
++)
441 fprintf (file
, " i%d", (int) i
);
443 for (i
= 0; i
< pdr_nb_params (pdr
); i
++)
444 fprintf (file
, " p%d", (int) i
);
446 fprintf (file
, " alias");
448 for (i
= 0; i
< PDR_NB_SUBSCRIPTS (pdr
); i
++)
449 fprintf (file
, " sub%d", (int) i
);
451 fprintf (file
, " cst\n");
454 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
458 print_pdr (FILE *file
, poly_dr_p pdr
, int verbosity
)
462 fprintf (file
, "# pdr_%d (", PDR_ID (pdr
));
464 switch (PDR_TYPE (pdr
))
467 fprintf (file
, "read \n");
471 fprintf (file
, "write \n");
475 fprintf (file
, "may_write \n");
482 dump_data_reference (file
, (data_reference_p
) PDR_CDR (pdr
));
487 fprintf (file
, "# data accesses (\n");
488 print_pdr_access_layout (file
, pdr
);
491 ppl_print_powerset_matrix (file
, PDR_ACCESSES (pdr
));
494 fprintf (file
, "#)\n");
497 fprintf (file
, "#)\n");
500 /* Prints to STDERR the polyhedral data reference PDR, at some
504 debug_pdr (poly_dr_p pdr
, int verbosity
)
506 print_pdr (stderr
, pdr
, verbosity
);
509 /* Creates a new SCOP containing REGION. */
512 new_scop (void *region
)
514 scop_p scop
= XNEW (struct scop
);
516 SCOP_CONTEXT (scop
) = NULL
;
517 scop_set_region (scop
, region
);
518 SCOP_BBS (scop
) = VEC_alloc (poly_bb_p
, heap
, 3);
519 SCOP_ORIGINAL_PDDRS (scop
) = htab_create (10, hash_poly_ddr_p
,
520 eq_poly_ddr_p
, free_poly_ddr
);
521 SCOP_ORIGINAL_SCHEDULE (scop
) = NULL
;
522 SCOP_TRANSFORMED_SCHEDULE (scop
) = NULL
;
523 SCOP_SAVED_SCHEDULE (scop
) = NULL
;
524 POLY_SCOP_P (scop
) = false;
532 free_scop (scop_p scop
)
537 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
540 VEC_free (poly_bb_p
, heap
, SCOP_BBS (scop
));
542 if (SCOP_CONTEXT (scop
))
543 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop
));
545 htab_delete (SCOP_ORIGINAL_PDDRS (scop
));
546 free_lst (SCOP_ORIGINAL_SCHEDULE (scop
));
547 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
548 free_lst (SCOP_SAVED_SCHEDULE (scop
));
552 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
555 print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
558 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
560 if (!PBB_DOMAIN (pbb
))
565 fprintf (file
, "# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
566 fprintf (file
, "# eq");
568 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
569 fprintf (file
, " i%d", (int) i
);
571 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
572 fprintf (file
, " p%d", (int) i
);
574 fprintf (file
, " cst\n");
577 if (PBB_DOMAIN (pbb
))
578 ppl_print_powerset_matrix (file
, PBB_DOMAIN (pbb
));
580 fprintf (file
, "0\n");
583 fprintf (file
, "#)\n");
586 /* Dump the cases of a graphite basic block GBB on FILE. */
589 dump_gbb_cases (FILE *file
, gimple_bb_p gbb
)
593 VEC (gimple
, heap
) *cases
;
598 cases
= GBB_CONDITION_CASES (gbb
);
599 if (VEC_empty (gimple
, cases
))
602 fprintf (file
, "# cases bb_%d (\n", GBB_BB (gbb
)->index
);
604 for (i
= 0; VEC_iterate (gimple
, cases
, i
, stmt
); i
++)
606 fprintf (file
, "# ");
607 print_gimple_stmt (file
, stmt
, 0, 0);
610 fprintf (file
, "#)\n");
613 /* Dump conditions of a graphite basic block GBB on FILE. */
616 dump_gbb_conditions (FILE *file
, gimple_bb_p gbb
)
620 VEC (gimple
, heap
) *conditions
;
625 conditions
= GBB_CONDITIONS (gbb
);
626 if (VEC_empty (gimple
, conditions
))
629 fprintf (file
, "# conditions bb_%d (\n", GBB_BB (gbb
)->index
);
631 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
633 fprintf (file
, "# ");
634 print_gimple_stmt (file
, stmt
, 0, 0);
637 fprintf (file
, "#)\n");
640 /* Print to FILE all the data references of PBB, at some VERBOSITY
644 print_pdrs (FILE *file
, poly_bb_p pbb
, int verbosity
)
651 if (VEC_length (poly_dr_p
, PBB_DRS (pbb
)) == 0)
654 fprintf (file
, "# Access informations are not provided\n");\
655 fprintf (file
, "0\n");
660 fprintf (file
, "# Data references (\n");
663 fprintf (file
, "# Access informations are provided\n");
664 fprintf (file
, "1\n");
666 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
667 if (PDR_TYPE (pdr
) == PDR_READ
)
673 fprintf (file
, "# Read data references (\n");
676 fprintf (file
, "# Read access informations\n");
677 fprintf (file
, "%d\n", nb_reads
);
679 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
680 if (PDR_TYPE (pdr
) == PDR_READ
)
681 print_pdr (file
, pdr
, verbosity
);
684 fprintf (file
, "#)\n");
687 fprintf (file
, "# Write data references (\n");
690 fprintf (file
, "# Write access informations\n");
691 fprintf (file
, "%d\n", nb_writes
);
693 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
694 if (PDR_TYPE (pdr
) != PDR_READ
)
695 print_pdr (file
, pdr
, verbosity
);
698 fprintf (file
, "#)\n");
701 fprintf (file
, "#)\n");
704 /* Print to STDERR all the data references of PBB. */
707 debug_pdrs (poly_bb_p pbb
, int verbosity
)
709 print_pdrs (stderr
, pbb
, verbosity
);
712 /* Print to FILE the body of PBB, at some VERBOSITY level. */
715 print_pbb_body (FILE *file
, poly_bb_p pbb
, int verbosity
)
718 fprintf (file
, "# Body (\n");
721 fprintf (file
, "# Statement body is provided\n");
722 fprintf (file
, "1\n");
725 fprintf (file
, "# Original iterator names\n# Iterator names are not provided yet.\n");
728 fprintf (file
, "# Statement body\n");
730 fprintf (file
, "{\n");
731 dump_bb (pbb_bb (pbb
), file
, 0);
732 fprintf (file
, "}\n");
735 fprintf (file
, "#)\n");
738 /* Print to FILE the domain and scattering function of PBB, at some
742 print_pbb (FILE *file
, poly_bb_p pbb
, int verbosity
)
746 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
747 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
748 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
751 print_pbb_domain (file
, pbb
, verbosity
);
752 print_scattering_function (file
, pbb
, verbosity
);
753 print_pdrs (file
, pbb
, verbosity
);
754 print_pbb_body (file
, pbb
, verbosity
);
757 fprintf (file
, "#)\n");
760 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
763 print_scop_params (FILE *file
, scop_p scop
, int verbosity
)
769 fprintf (file
, "# parameters (\n");
771 if (VEC_length (tree
, SESE_PARAMS (SCOP_REGION (scop
))))
774 fprintf (file
, "# Parameter names are provided\n");
776 fprintf (file
, "1\n");
779 fprintf (file
, "# Parameter names\n");
784 fprintf (file
, "# Parameter names are not provided\n");
785 fprintf (file
, "0\n");
788 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (SCOP_REGION (scop
)), i
, t
); i
++)
790 print_generic_expr (file
, t
, 0);
794 fprintf (file
, "\n");
797 fprintf (file
, "#)\n");
800 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
803 print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
809 fprintf (file
, "# Context (\n");
810 fprintf (file
, "# eq");
812 for (i
= 0; i
< scop_nb_params (scop
); i
++)
813 fprintf (file
, " p%d", (int) i
);
815 fprintf (file
, " cst\n");
818 if (SCOP_CONTEXT (scop
))
819 ppl_print_powerset_matrix (file
, SCOP_CONTEXT (scop
));
821 fprintf (file
, "0 %d\n", (int) scop_nb_params (scop
) + 2);
824 fprintf (file
, "# )\n");
827 /* Print to FILE the SCOP, at some VERBOSITY level. */
830 print_scop (FILE *file
, scop_p scop
, int verbosity
)
835 fprintf (file
, "SCoP #(\n");
836 fprintf (file
, "# Language\nGimple\n");
837 print_scop_context (file
, scop
, verbosity
);
838 print_scop_params (file
, scop
, verbosity
);
841 fprintf (file
, "# Number of statements\n");
843 fprintf (file
, "%d\n",VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
845 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
846 print_pbb (file
, pbb
, verbosity
);
850 fprintf (file
, "# original_lst (\n");
851 print_lst (file
, SCOP_ORIGINAL_SCHEDULE (scop
), 0);
852 fprintf (file
, "\n#)\n");
854 fprintf (file
, "# transformed_lst (\n");
855 print_lst (file
, SCOP_TRANSFORMED_SCHEDULE (scop
), 0);
856 fprintf (file
, "\n#)\n");
859 fprintf (file
, "#)\n");
862 /* Print to FILE the input file that CLooG would expect as input, at
863 some VERBOSITY level. */
866 print_cloog (FILE *file
, scop_p scop
, int verbosity
)
871 fprintf (file
, "# SCoP (generated by GCC/Graphite\n");
873 fprintf (file
, "# CLooG output language\n");
874 fprintf (file
, "c\n");
876 print_scop_context (file
, scop
, verbosity
);
877 print_scop_params (file
, scop
, verbosity
);
880 fprintf (file
, "# Number of statements\n");
882 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
884 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
887 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
889 print_pbb_domain (file
, pbb
, verbosity
);
890 fprintf (file
, "0 0 0");
893 fprintf (file
, "# For future CLooG options.\n");
895 fprintf (file
, "\n");
898 fprintf (file
, "#)\n");
903 fprintf (file
, "# Don't set the iterator names.\n");
905 fprintf (file
, "\n");
908 fprintf (file
, "# Number of scattering functions\n");
910 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
911 unify_scattering_dimensions (scop
);
913 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
915 if (!PBB_TRANSFORMED (pbb
)
916 || !(PBB_TRANSFORMED_SCATTERING (pbb
)
917 || PBB_ORIGINAL_SCATTERING (pbb
)))
921 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
923 print_scattering_function_1 (file
, pbb
, verbosity
);
926 fprintf (file
, "#)\n");
931 fprintf (file
, "# Don't set the scattering dimension names.\n");
933 fprintf (file
, "\n");
935 fprintf (file
, "#)\n");
938 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
941 debug_pbb_domain (poly_bb_p pbb
, int verbosity
)
943 print_pbb_domain (stderr
, pbb
, verbosity
);
946 /* Print to FILE the domain and scattering function of PBB, at some
950 debug_pbb (poly_bb_p pbb
, int verbosity
)
952 print_pbb (stderr
, pbb
, verbosity
);
955 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
958 debug_scop_context (scop_p scop
, int verbosity
)
960 print_scop_context (stderr
, scop
, verbosity
);
963 /* Print to STDERR the SCOP, at some VERBOSITY level. */
966 debug_scop (scop_p scop
, int verbosity
)
968 print_scop (stderr
, scop
, verbosity
);
971 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
975 debug_cloog (scop_p scop
, int verbosity
)
977 print_cloog (stderr
, scop
, verbosity
);
980 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
984 debug_scop_params (scop_p scop
, int verbosity
)
986 print_scop_params (stderr
, scop
, verbosity
);
990 /* The dimension in the transformed scattering polyhedron of PBB
991 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
994 psct_scattering_dim_for_loop_depth (poly_bb_p pbb
, graphite_dim_t loop_depth
)
996 ppl_const_Constraint_System_t pcs
;
997 ppl_Constraint_System_const_iterator_t cit
, cend
;
998 ppl_const_Constraint_t cstr
;
999 ppl_Polyhedron_t ph
= PBB_TRANSFORMED_SCATTERING (pbb
);
1000 ppl_dimension_type iter
= psct_iterator_dim (pbb
, loop_depth
);
1001 ppl_Linear_Expression_t expr
;
1002 ppl_Coefficient_t coef
;
1007 ppl_new_Coefficient (&coef
);
1008 ppl_Polyhedron_get_constraints (ph
, &pcs
);
1009 ppl_new_Constraint_System_const_iterator (&cit
);
1010 ppl_new_Constraint_System_const_iterator (&cend
);
1012 for (ppl_Constraint_System_begin (pcs
, cit
),
1013 ppl_Constraint_System_end (pcs
, cend
);
1014 !ppl_Constraint_System_const_iterator_equal_test (cit
, cend
);
1015 ppl_Constraint_System_const_iterator_increment (cit
))
1017 ppl_Constraint_System_const_iterator_dereference (cit
, &cstr
);
1018 ppl_new_Linear_Expression_from_Constraint (&expr
, cstr
);
1019 ppl_Linear_Expression_coefficient (expr
, iter
, coef
);
1020 ppl_Coefficient_to_mpz_t (coef
, val
);
1024 ppl_delete_Linear_Expression (expr
);
1028 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
1030 ppl_dimension_type scatter
= psct_scattering_dim (pbb
, i
);
1032 ppl_Linear_Expression_coefficient (expr
, scatter
, coef
);
1033 ppl_Coefficient_to_mpz_t (coef
, val
);
1035 if (mpz_sgn (val
) != 0)
1038 ppl_delete_Linear_Expression (expr
);
1039 ppl_delete_Coefficient (coef
);
1040 ppl_delete_Constraint_System_const_iterator (cit
);
1041 ppl_delete_Constraint_System_const_iterator (cend
);
1051 /* Returns the number of iterations NITER of the loop around PBB at
1052 depth LOOP_DEPTH. */
1055 pbb_number_of_iterations (poly_bb_p pbb
,
1056 graphite_dim_t loop_depth
,
1059 ppl_Linear_Expression_t le
;
1060 ppl_dimension_type dim
;
1062 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
), &dim
);
1063 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
1064 ppl_set_coef (le
, pbb_iterator_dim (pbb
, loop_depth
), 1);
1065 mpz_set_si (niter
, -1);
1066 ppl_max_for_le_pointset (PBB_DOMAIN (pbb
), le
, niter
);
1067 ppl_delete_Linear_Expression (le
);
1070 /* Returns the number of iterations NITER of the loop around PBB at
1071 time(scattering) dimension TIME_DEPTH. */
1074 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
1075 graphite_dim_t time_depth
,
1078 ppl_Pointset_Powerset_C_Polyhedron_t ext_domain
, sctr
;
1079 ppl_Linear_Expression_t le
;
1080 ppl_dimension_type dim
;
1082 /* Takes together domain and scattering polyhedrons, and composes
1083 them into the bigger polyhedron that has the following format:
1085 t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}
1088 | t0..t_{n-1} are time dimensions (scattering dimensions)
1089 | l0..l_{nclc-1} are local variables in scattering function
1090 | i0..i_{niter-1} are original iteration variables
1091 | g0..g_{nparam-1} are global parameters. */
1093 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr
,
1094 PBB_TRANSFORMED_SCATTERING (pbb
));
1096 /* Extend the iteration domain with the scattering dimensions:
1097 0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}. */
1098 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1099 (&ext_domain
, PBB_DOMAIN (pbb
));
1100 ppl_insert_dimensions_pointset (ext_domain
, 0,
1101 pbb_nb_scattering_transform (pbb
)
1102 + pbb_nb_local_vars (pbb
));
1104 /* Add to sctr the extended domain. */
1105 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr
, ext_domain
);
1107 /* Extract the number of iterations. */
1108 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr
, &dim
);
1109 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
1110 ppl_set_coef (le
, time_depth
, 1);
1111 mpz_set_si (niter
, -1);
1112 ppl_max_for_le_pointset (sctr
, le
, niter
);
1114 ppl_delete_Linear_Expression (le
);
1115 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr
);
1116 ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain
);
1119 /* Translates LOOP to LST. */
1122 loop_to_lst (loop_p loop
, VEC (poly_bb_p
, heap
) *bbs
, int *i
)
1125 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1127 for (; VEC_iterate (poly_bb_p
, bbs
, *i
, pbb
); (*i
)++)
1130 basic_block bb
= GBB_BB (PBB_BLACK_BOX (pbb
));
1132 if (bb
->loop_father
== loop
)
1133 stmt
= new_lst_stmt (pbb
);
1134 else if (flow_bb_inside_loop_p (loop
, bb
))
1136 loop_p next
= loop
->inner
;
1138 while (next
&& !flow_bb_inside_loop_p (next
, bb
))
1141 stmt
= loop_to_lst (next
, bbs
, i
);
1146 return new_lst_loop (seq
);
1149 VEC_safe_push (lst_p
, heap
, seq
, stmt
);
1152 return new_lst_loop (seq
);
1155 /* Reads the original scattering of the SCOP and returns an LST
1159 scop_to_lst (scop_p scop
)
1162 int i
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
1163 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1164 sese region
= SCOP_REGION (scop
);
1166 for (i
= 0; i
< n
; i
++)
1168 poly_bb_p pbb
= VEC_index (poly_bb_p
, SCOP_BBS (scop
), i
);
1169 loop_p loop
= outermost_loop_in_sese (region
, GBB_BB (PBB_BLACK_BOX (pbb
)));
1171 if (loop_in_sese_p (loop
, region
))
1172 res
= loop_to_lst (loop
, SCOP_BBS (scop
), &i
);
1174 res
= new_lst_stmt (pbb
);
1176 VEC_safe_push (lst_p
, heap
, seq
, res
);
1179 res
= new_lst_loop (seq
);
1180 SCOP_ORIGINAL_SCHEDULE (scop
) = res
;
1181 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (res
);
1184 /* Print to FILE on a new line COLUMN white spaces. */
1187 lst_indent_to (FILE *file
, int column
)
1192 fprintf (file
, "\n#");
1194 for (i
= 0; i
< column
; i
++)
1195 fprintf (file
, " ");
1198 /* Print LST to FILE with INDENT spaces of indentation. */
1201 print_lst (FILE *file
, lst_p lst
, int indent
)
1206 lst_indent_to (file
, indent
);
1208 if (LST_LOOP_P (lst
))
1213 if (LST_LOOP_FATHER (lst
))
1214 fprintf (file
, "%d (loop", lst_dewey_number (lst
));
1216 fprintf (file
, "#(root");
1218 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1219 print_lst (file
, l
, indent
+ 2);
1221 fprintf (file
, ")");
1224 fprintf (file
, "%d stmt_%d", lst_dewey_number (lst
), pbb_index (LST_PBB (lst
)));
1227 /* Print LST to STDERR. */
1230 debug_lst (lst_p lst
)
1232 print_lst (stderr
, lst
, 0);
1235 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1238 dot_lst_1 (FILE *file
, lst_p lst
)
1243 if (LST_LOOP_P (lst
))
1248 if (!LST_LOOP_FATHER (lst
))
1249 fprintf (file
, "L -> L_%d_%d\n",
1251 lst_dewey_number (lst
));
1253 fprintf (file
, "L_%d_%d -> L_%d_%d\n",
1254 lst_depth (LST_LOOP_FATHER (lst
)),
1255 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1257 lst_dewey_number (lst
));
1259 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1260 dot_lst_1 (file
, l
);
1264 fprintf (file
, "L_%d_%d -> S_%d\n",
1265 lst_depth (LST_LOOP_FATHER (lst
)),
1266 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1267 pbb_index (LST_PBB (lst
)));
1271 /* Display the LST using dotty. */
1276 /* When debugging, enable the following code. This cannot be used
1277 in production compilers because it calls "system". */
1280 FILE *stream
= fopen ("/tmp/lst.dot", "w");
1281 gcc_assert (stream
);
1283 fputs ("digraph all {\n", stream
);
1284 dot_lst_1 (stream
, lst
);
1285 fputs ("}\n\n", stream
);
1288 x
= system ("dotty /tmp/lst.dot &");
1290 fputs ("digraph all {\n", stderr
);
1291 dot_lst_1 (stderr
, lst
);
1292 fputs ("}\n\n", stderr
);