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"
51 #include "graphite-ppl.h"
53 #include "graphite-poly.h"
54 #include "graphite-dependences.h"
56 /* Return the maximal loop depth in SCOP. */
59 scop_max_loop_depth (scop_p scop
)
65 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
67 int nb_loops
= pbb_dim_iter_domain (pbb
);
68 if (max_nb_loops
< nb_loops
)
69 max_nb_loops
= nb_loops
;
75 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
79 extend_scattering (poly_bb_p pbb
, int max_scattering
)
81 ppl_dimension_type nb_old_dims
, nb_new_dims
;
83 ppl_Coefficient_t coef
;
86 nb_added_dims
= max_scattering
- pbb_nb_scattering_transform (pbb
);
89 ppl_new_Coefficient (&coef
);
90 ppl_assign_Coefficient_from_mpz_t (coef
, one
);
92 gcc_assert (nb_added_dims
>= 0);
94 nb_old_dims
= pbb_nb_scattering_transform (pbb
) + pbb_dim_iter_domain (pbb
)
95 + scop_nb_params (PBB_SCOP (pbb
));
96 nb_new_dims
= nb_old_dims
+ nb_added_dims
;
98 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
),
99 pbb_nb_scattering_transform (pbb
), nb_added_dims
);
100 PBB_NB_SCATTERING_TRANSFORM (pbb
) += nb_added_dims
;
102 /* Add identity matrix for the added dimensions. */
103 for (i
= max_scattering
- nb_added_dims
; i
< max_scattering
; i
++)
105 ppl_Constraint_t cstr
;
106 ppl_Linear_Expression_t expr
;
108 ppl_new_Linear_Expression_with_dimension (&expr
, nb_new_dims
);
109 ppl_Linear_Expression_add_to_coefficient (expr
, i
, coef
);
110 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
111 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
112 ppl_delete_Constraint (cstr
);
113 ppl_delete_Linear_Expression (expr
);
116 ppl_delete_Coefficient (coef
);
120 /* All scattering matrices in SCOP will have the same number of scattering
124 unify_scattering_dimensions (scop_p scop
)
128 graphite_dim_t max_scattering
= 0;
130 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
131 max_scattering
= MAX (pbb_nb_scattering_transform (pbb
), max_scattering
);
133 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
134 extend_scattering (pbb
, max_scattering
);
136 return max_scattering
;
139 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
143 print_scattering_function_1 (FILE *file
, poly_bb_p pbb
, int verbosity
)
149 fprintf (file
, "# scattering bb_%d (\n", pbb_index (pbb
));
150 fprintf (file
, "# eq");
152 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
153 fprintf (file
, " s%d", (int) i
);
155 for (i
= 0; i
< pbb_nb_local_vars (pbb
); i
++)
156 fprintf (file
, " lv%d", (int) i
);
158 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
159 fprintf (file
, " i%d", (int) i
);
161 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
162 fprintf (file
, " p%d", (int) i
);
164 fprintf (file
, " cst\n");
167 /* Number of disjunct components. Remove this when
168 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
169 fprintf (file
, "1\n");
170 ppl_print_polyhedron_matrix (file
, PBB_TRANSFORMED_SCATTERING (pbb
)
171 ? PBB_TRANSFORMED_SCATTERING (pbb
)
172 : PBB_ORIGINAL_SCATTERING (pbb
));
175 fprintf (file
, "#)\n");
178 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
182 print_scattering_function (FILE *file
, poly_bb_p pbb
, int verbosity
)
184 if (!PBB_TRANSFORMED (pbb
))
187 if (PBB_TRANSFORMED_SCATTERING (pbb
)
188 || PBB_ORIGINAL_SCATTERING (pbb
))
191 fprintf (file
, "# Scattering function is provided\n");
193 fprintf (file
, "1\n");
198 fprintf (file
, "# Scattering function is not provided\n");
200 fprintf (file
, "0\n");
204 print_scattering_function_1 (file
, pbb
, verbosity
);
207 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
211 print_iteration_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
213 print_pbb_domain (file
, pbb
, verbosity
);
216 /* Prints to FILE the scattering functions of every PBB of SCOP. */
219 print_scattering_functions (FILE *file
, scop_p scop
, int verbosity
)
224 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
225 print_scattering_function (file
, pbb
, verbosity
);
228 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
232 print_iteration_domains (FILE *file
, scop_p scop
, int verbosity
)
237 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
238 print_iteration_domain (file
, pbb
, verbosity
);
241 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
245 debug_scattering_function (poly_bb_p pbb
, int verbosity
)
247 print_scattering_function (stderr
, pbb
, verbosity
);
250 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
254 debug_iteration_domain (poly_bb_p pbb
, int verbosity
)
256 print_iteration_domain (stderr
, pbb
, verbosity
);
259 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
260 some VERBOSITY level. */
263 debug_scattering_functions (scop_p scop
, int verbosity
)
265 print_scattering_functions (stderr
, scop
, verbosity
);
268 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
269 some VERBOSITY level. */
272 debug_iteration_domains (scop_p scop
, int verbosity
)
274 print_iteration_domains (stderr
, scop
, verbosity
);
278 /* Apply graphite transformations to all the basic blocks of SCOP. */
281 apply_poly_transforms (scop_p scop
)
283 bool transform_done
= false;
285 /* Generate code even if we did not apply any real transformation.
286 This also allows to check the performance for the identity
287 transformation: GIMPLE -> GRAPHITE -> GIMPLE
288 Keep in mind that CLooG optimizes in control, so the loop structure
289 may change, even if we only use -fgraphite-identity. */
290 if (flag_graphite_identity
)
291 transform_done
= true;
293 if (flag_loop_parallelize_all
)
294 transform_done
= true;
297 transform_done
|= scop_do_block (scop
);
300 if (flag_loop_strip_mine
)
301 transform_done
|= scop_do_strip_mine (scop
);
303 if (flag_loop_interchange
)
304 transform_done
|= scop_do_interchange (scop
);
307 return transform_done
;
310 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
311 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */
314 can_collapse_pdrs (poly_dr_p pdr1
, poly_dr_p pdr2
)
317 ppl_Pointset_Powerset_C_Polyhedron_t af1
, af2
, diff
;
319 if (PDR_PBB (pdr1
) != PDR_PBB (pdr2
)
320 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
)
321 || PDR_TYPE (pdr1
) != PDR_TYPE (pdr2
))
324 af1
= PDR_ACCESSES (pdr1
);
325 af2
= PDR_ACCESSES (pdr2
);
326 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
328 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff
, af2
);
330 res
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff
);
331 ppl_delete_Pointset_Powerset_C_Polyhedron (diff
);
335 /* Removes duplicated data references in PBB. */
338 pbb_remove_duplicate_pdrs (poly_bb_p pbb
)
341 poly_dr_p pdr1
, pdr2
;
342 unsigned n
= VEC_length (poly_dr_p
, PBB_DRS (pbb
));
343 VEC (poly_dr_p
, heap
) *collapsed
= VEC_alloc (poly_dr_p
, heap
, n
);
345 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr1
); i
++)
346 for (j
= 0; VEC_iterate (poly_dr_p
, collapsed
, j
, pdr2
); j
++)
347 if (!can_collapse_pdrs (pdr1
, pdr2
))
348 VEC_quick_push (poly_dr_p
, collapsed
, pdr1
);
350 VEC_free (poly_dr_p
, heap
, collapsed
);
351 PBB_PDR_DUPLICATES_REMOVED (pbb
) = true;
354 /* Create a new polyhedral data reference and add it to PBB. It is
355 defined by its ACCESSES, its TYPE, and the number of subscripts
359 new_poly_dr (poly_bb_p pbb
, int dr_base_object_set
,
360 ppl_Pointset_Powerset_C_Polyhedron_t accesses
,
361 enum poly_dr_type type
, void *cdr
, graphite_dim_t nb_subscripts
)
364 poly_dr_p pdr
= XNEW (struct poly_dr
);
367 PDR_BASE_OBJECT_SET (pdr
) = dr_base_object_set
;
368 PDR_NB_REFS (pdr
) = 1;
370 PDR_ACCESSES (pdr
) = accesses
;
371 PDR_TYPE (pdr
) = type
;
373 PDR_NB_SUBSCRIPTS (pdr
) = nb_subscripts
;
374 VEC_safe_push (poly_dr_p
, heap
, PBB_DRS (pbb
), pdr
);
377 /* Free polyhedral data reference PDR. */
380 free_poly_dr (poly_dr_p pdr
)
382 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr
));
386 /* Create a new polyhedral black box. */
389 new_poly_bb (scop_p scop
, void *black_box
, bool reduction
)
391 poly_bb_p pbb
= XNEW (struct poly_bb
);
393 PBB_DOMAIN (pbb
) = NULL
;
394 PBB_SCOP (pbb
) = scop
;
395 pbb_set_black_box (pbb
, black_box
);
396 PBB_TRANSFORMED (pbb
) = NULL
;
397 PBB_SAVED (pbb
) = NULL
;
398 PBB_ORIGINAL (pbb
) = NULL
;
399 PBB_DRS (pbb
) = VEC_alloc (poly_dr_p
, heap
, 3);
400 PBB_IS_REDUCTION (pbb
) = reduction
;
401 PBB_PDR_DUPLICATES_REMOVED (pbb
) = false;
402 VEC_safe_push (poly_bb_p
, heap
, SCOP_BBS (scop
), pbb
);
405 /* Free polyhedral black box. */
408 free_poly_bb (poly_bb_p pbb
)
413 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb
));
415 if (PBB_TRANSFORMED (pbb
))
416 poly_scattering_free (PBB_TRANSFORMED (pbb
));
419 poly_scattering_free (PBB_SAVED (pbb
));
421 if (PBB_ORIGINAL (pbb
))
422 poly_scattering_free (PBB_ORIGINAL (pbb
));
425 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
428 VEC_free (poly_dr_p
, heap
, PBB_DRS (pbb
));
433 print_pdr_access_layout (FILE *file
, poly_dr_p pdr
)
437 fprintf (file
, "# eq");
439 for (i
= 0; i
< pdr_dim_iter_domain (pdr
); i
++)
440 fprintf (file
, " i%d", (int) i
);
442 for (i
= 0; i
< pdr_nb_params (pdr
); i
++)
443 fprintf (file
, " p%d", (int) i
);
445 fprintf (file
, " alias");
447 for (i
= 0; i
< PDR_NB_SUBSCRIPTS (pdr
); i
++)
448 fprintf (file
, " sub%d", (int) i
);
450 fprintf (file
, " cst\n");
453 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
457 print_pdr (FILE *file
, poly_dr_p pdr
, int verbosity
)
461 fprintf (file
, "# pdr_%d (", PDR_ID (pdr
));
463 switch (PDR_TYPE (pdr
))
466 fprintf (file
, "read \n");
470 fprintf (file
, "write \n");
474 fprintf (file
, "may_write \n");
481 dump_data_reference (file
, (data_reference_p
) PDR_CDR (pdr
));
486 fprintf (file
, "# data accesses (\n");
487 print_pdr_access_layout (file
, pdr
);
490 ppl_print_powerset_matrix (file
, PDR_ACCESSES (pdr
));
493 fprintf (file
, "#)\n");
496 fprintf (file
, "#)\n");
499 /* Prints to STDERR the polyhedral data reference PDR, at some
503 debug_pdr (poly_dr_p pdr
, int verbosity
)
505 print_pdr (stderr
, pdr
, verbosity
);
508 /* Creates a new SCOP containing REGION. */
511 new_scop (void *region
)
513 scop_p scop
= XNEW (struct scop
);
515 SCOP_CONTEXT (scop
) = NULL
;
516 scop_set_region (scop
, region
);
517 SCOP_BBS (scop
) = VEC_alloc (poly_bb_p
, heap
, 3);
518 SCOP_ORIGINAL_PDDRS (scop
) = htab_create (10, hash_poly_ddr_p
,
519 eq_poly_ddr_p
, free_poly_ddr
);
520 SCOP_ORIGINAL_SCHEDULE (scop
) = NULL
;
521 SCOP_TRANSFORMED_SCHEDULE (scop
) = NULL
;
522 SCOP_SAVED_SCHEDULE (scop
) = NULL
;
523 POLY_SCOP_P (scop
) = false;
531 free_scop (scop_p scop
)
536 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
539 VEC_free (poly_bb_p
, heap
, SCOP_BBS (scop
));
541 if (SCOP_CONTEXT (scop
))
542 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop
));
544 htab_delete (SCOP_ORIGINAL_PDDRS (scop
));
545 free_lst (SCOP_ORIGINAL_SCHEDULE (scop
));
546 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
547 free_lst (SCOP_SAVED_SCHEDULE (scop
));
551 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
554 print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
557 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
559 if (!PBB_DOMAIN (pbb
))
564 fprintf (file
, "# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
565 fprintf (file
, "# eq");
567 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
568 fprintf (file
, " i%d", (int) i
);
570 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
571 fprintf (file
, " p%d", (int) i
);
573 fprintf (file
, " cst\n");
576 if (PBB_DOMAIN (pbb
))
577 ppl_print_powerset_matrix (file
, PBB_DOMAIN (pbb
));
579 fprintf (file
, "0\n");
582 fprintf (file
, "#)\n");
585 /* Dump the cases of a graphite basic block GBB on FILE. */
588 dump_gbb_cases (FILE *file
, gimple_bb_p gbb
)
592 VEC (gimple
, heap
) *cases
;
597 cases
= GBB_CONDITION_CASES (gbb
);
598 if (VEC_empty (gimple
, cases
))
601 fprintf (file
, "# cases bb_%d (\n", GBB_BB (gbb
)->index
);
603 for (i
= 0; VEC_iterate (gimple
, cases
, i
, stmt
); i
++)
605 fprintf (file
, "# ");
606 print_gimple_stmt (file
, stmt
, 0, 0);
609 fprintf (file
, "#)\n");
612 /* Dump conditions of a graphite basic block GBB on FILE. */
615 dump_gbb_conditions (FILE *file
, gimple_bb_p gbb
)
619 VEC (gimple
, heap
) *conditions
;
624 conditions
= GBB_CONDITIONS (gbb
);
625 if (VEC_empty (gimple
, conditions
))
628 fprintf (file
, "# conditions bb_%d (\n", GBB_BB (gbb
)->index
);
630 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
632 fprintf (file
, "# ");
633 print_gimple_stmt (file
, stmt
, 0, 0);
636 fprintf (file
, "#)\n");
639 /* Print to FILE all the data references of PBB, at some VERBOSITY
643 print_pdrs (FILE *file
, poly_bb_p pbb
, int verbosity
)
650 if (VEC_length (poly_dr_p
, PBB_DRS (pbb
)) == 0)
653 fprintf (file
, "# Access informations are not provided\n");\
654 fprintf (file
, "0\n");
659 fprintf (file
, "# Data references (\n");
662 fprintf (file
, "# Access informations are provided\n");
663 fprintf (file
, "1\n");
665 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
666 if (PDR_TYPE (pdr
) == PDR_READ
)
672 fprintf (file
, "# Read data references (\n");
675 fprintf (file
, "# Read access informations\n");
676 fprintf (file
, "%d\n", nb_reads
);
678 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
679 if (PDR_TYPE (pdr
) == PDR_READ
)
680 print_pdr (file
, pdr
, verbosity
);
683 fprintf (file
, "#)\n");
686 fprintf (file
, "# Write data references (\n");
689 fprintf (file
, "# Write access informations\n");
690 fprintf (file
, "%d\n", nb_writes
);
692 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
693 if (PDR_TYPE (pdr
) != PDR_READ
)
694 print_pdr (file
, pdr
, verbosity
);
697 fprintf (file
, "#)\n");
700 fprintf (file
, "#)\n");
703 /* Print to STDERR all the data references of PBB. */
706 debug_pdrs (poly_bb_p pbb
, int verbosity
)
708 print_pdrs (stderr
, pbb
, verbosity
);
711 /* Print to FILE the body of PBB, at some VERBOSITY level. */
714 print_pbb_body (FILE *file
, poly_bb_p pbb
, int verbosity
)
717 fprintf (file
, "# Body (\n");
720 fprintf (file
, "# Statement body is provided\n");
721 fprintf (file
, "1\n");
724 fprintf (file
, "# Original iterator names\n# Iterator names are not provided yet.\n");
727 fprintf (file
, "# Statement body\n");
729 fprintf (file
, "{\n");
730 dump_bb (pbb_bb (pbb
), file
, 0);
731 fprintf (file
, "}\n");
734 fprintf (file
, "#)\n");
737 /* Print to FILE the domain and scattering function of PBB, at some
741 print_pbb (FILE *file
, poly_bb_p pbb
, int verbosity
)
745 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
746 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
747 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
750 print_pbb_domain (file
, pbb
, verbosity
);
751 print_scattering_function (file
, pbb
, verbosity
);
752 print_pdrs (file
, pbb
, verbosity
);
753 print_pbb_body (file
, pbb
, verbosity
);
756 fprintf (file
, "#)\n");
759 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
762 print_scop_params (FILE *file
, scop_p scop
, int verbosity
)
768 fprintf (file
, "# parameters (\n");
770 if (VEC_length (tree
, SESE_PARAMS (SCOP_REGION (scop
))))
773 fprintf (file
, "# Parameter names are provided\n");
775 fprintf (file
, "1\n");
778 fprintf (file
, "# Parameter names\n");
783 fprintf (file
, "# Parameter names are not provided\n");
784 fprintf (file
, "0\n");
787 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (SCOP_REGION (scop
)), i
, t
); i
++)
789 print_generic_expr (file
, t
, 0);
793 fprintf (file
, "\n");
796 fprintf (file
, "#)\n");
799 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
802 print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
808 fprintf (file
, "# Context (\n");
809 fprintf (file
, "# eq");
811 for (i
= 0; i
< scop_nb_params (scop
); i
++)
812 fprintf (file
, " p%d", (int) i
);
814 fprintf (file
, " cst\n");
817 if (SCOP_CONTEXT (scop
))
818 ppl_print_powerset_matrix (file
, SCOP_CONTEXT (scop
));
820 fprintf (file
, "0 %d\n", (int) scop_nb_params (scop
) + 2);
823 fprintf (file
, "# )\n");
826 /* Print to FILE the SCOP, at some VERBOSITY level. */
829 print_scop (FILE *file
, scop_p scop
, int verbosity
)
834 fprintf (file
, "SCoP #(\n");
835 fprintf (file
, "# Language\nGimple\n");
836 print_scop_context (file
, scop
, verbosity
);
837 print_scop_params (file
, scop
, verbosity
);
840 fprintf (file
, "# Number of statements\n");
842 fprintf (file
, "%d\n",VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
844 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
845 print_pbb (file
, pbb
, verbosity
);
849 fprintf (file
, "# original_lst (\n");
850 print_lst (file
, SCOP_ORIGINAL_SCHEDULE (scop
), 0);
851 fprintf (file
, "\n#)\n");
853 fprintf (file
, "# transformed_lst (\n");
854 print_lst (file
, SCOP_TRANSFORMED_SCHEDULE (scop
), 0);
855 fprintf (file
, "\n#)\n");
858 fprintf (file
, "#)\n");
861 /* Print to FILE the input file that CLooG would expect as input, at
862 some VERBOSITY level. */
865 print_cloog (FILE *file
, scop_p scop
, int verbosity
)
870 fprintf (file
, "# SCoP (generated by GCC/Graphite\n");
872 fprintf (file
, "# CLooG output language\n");
873 fprintf (file
, "c\n");
875 print_scop_context (file
, scop
, verbosity
);
876 print_scop_params (file
, scop
, verbosity
);
879 fprintf (file
, "# Number of statements\n");
881 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
883 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
886 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
888 print_pbb_domain (file
, pbb
, verbosity
);
889 fprintf (file
, "0 0 0");
892 fprintf (file
, "# For future CLooG options.\n");
894 fprintf (file
, "\n");
897 fprintf (file
, "#)\n");
902 fprintf (file
, "# Don't set the iterator names.\n");
904 fprintf (file
, "\n");
907 fprintf (file
, "# Number of scattering functions\n");
909 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
910 unify_scattering_dimensions (scop
);
912 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
914 if (!PBB_TRANSFORMED (pbb
)
915 || !(PBB_TRANSFORMED_SCATTERING (pbb
)
916 || PBB_ORIGINAL_SCATTERING (pbb
)))
920 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
922 print_scattering_function_1 (file
, pbb
, verbosity
);
925 fprintf (file
, "#)\n");
930 fprintf (file
, "# Don't set the scattering dimension names.\n");
932 fprintf (file
, "\n");
934 fprintf (file
, "#)\n");
937 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
940 debug_pbb_domain (poly_bb_p pbb
, int verbosity
)
942 print_pbb_domain (stderr
, pbb
, verbosity
);
945 /* Print to FILE the domain and scattering function of PBB, at some
949 debug_pbb (poly_bb_p pbb
, int verbosity
)
951 print_pbb (stderr
, pbb
, verbosity
);
954 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
957 debug_scop_context (scop_p scop
, int verbosity
)
959 print_scop_context (stderr
, scop
, verbosity
);
962 /* Print to STDERR the SCOP, at some VERBOSITY level. */
965 debug_scop (scop_p scop
, int verbosity
)
967 print_scop (stderr
, scop
, verbosity
);
970 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
974 debug_cloog (scop_p scop
, int verbosity
)
976 print_cloog (stderr
, scop
, verbosity
);
979 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
983 debug_scop_params (scop_p scop
, int verbosity
)
985 print_scop_params (stderr
, scop
, verbosity
);
989 /* The dimension in the transformed scattering polyhedron of PBB
990 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
993 psct_scattering_dim_for_loop_depth (poly_bb_p pbb
, graphite_dim_t loop_depth
)
995 ppl_const_Constraint_System_t pcs
;
996 ppl_Constraint_System_const_iterator_t cit
, cend
;
997 ppl_const_Constraint_t cstr
;
998 ppl_Polyhedron_t ph
= PBB_TRANSFORMED_SCATTERING (pbb
);
999 ppl_dimension_type iter
= psct_iterator_dim (pbb
, loop_depth
);
1000 ppl_Linear_Expression_t expr
;
1001 ppl_Coefficient_t coef
;
1006 ppl_new_Coefficient (&coef
);
1007 ppl_Polyhedron_get_constraints (ph
, &pcs
);
1008 ppl_new_Constraint_System_const_iterator (&cit
);
1009 ppl_new_Constraint_System_const_iterator (&cend
);
1011 for (ppl_Constraint_System_begin (pcs
, cit
),
1012 ppl_Constraint_System_end (pcs
, cend
);
1013 !ppl_Constraint_System_const_iterator_equal_test (cit
, cend
);
1014 ppl_Constraint_System_const_iterator_increment (cit
))
1016 ppl_Constraint_System_const_iterator_dereference (cit
, &cstr
);
1017 ppl_new_Linear_Expression_from_Constraint (&expr
, cstr
);
1018 ppl_Linear_Expression_coefficient (expr
, iter
, coef
);
1019 ppl_Coefficient_to_mpz_t (coef
, val
);
1023 ppl_delete_Linear_Expression (expr
);
1027 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
1029 ppl_dimension_type scatter
= psct_scattering_dim (pbb
, i
);
1031 ppl_Linear_Expression_coefficient (expr
, scatter
, coef
);
1032 ppl_Coefficient_to_mpz_t (coef
, val
);
1034 if (mpz_sgn (val
) != 0)
1037 ppl_delete_Linear_Expression (expr
);
1038 ppl_delete_Coefficient (coef
);
1039 ppl_delete_Constraint_System_const_iterator (cit
);
1040 ppl_delete_Constraint_System_const_iterator (cend
);
1050 /* Returns the number of iterations NITER of the loop around PBB at
1051 depth LOOP_DEPTH. */
1054 pbb_number_of_iterations (poly_bb_p pbb
,
1055 graphite_dim_t loop_depth
,
1058 ppl_Linear_Expression_t le
;
1059 ppl_dimension_type dim
;
1061 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
), &dim
);
1062 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
1063 ppl_set_coef (le
, pbb_iterator_dim (pbb
, loop_depth
), 1);
1064 mpz_set_si (niter
, -1);
1065 ppl_max_for_le_pointset (PBB_DOMAIN (pbb
), le
, niter
);
1066 ppl_delete_Linear_Expression (le
);
1069 /* Returns the number of iterations NITER of the loop around PBB at
1070 time(scattering) dimension TIME_DEPTH. */
1073 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
1074 graphite_dim_t time_depth
,
1077 ppl_Pointset_Powerset_C_Polyhedron_t ext_domain
, sctr
;
1078 ppl_Linear_Expression_t le
;
1079 ppl_dimension_type dim
;
1081 /* Takes together domain and scattering polyhedrons, and composes
1082 them into the bigger polyhedron that has the following format:
1084 t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}
1087 | t0..t_{n-1} are time dimensions (scattering dimensions)
1088 | l0..l_{nclc-1} are local variables in scattering function
1089 | i0..i_{niter-1} are original iteration variables
1090 | g0..g_{nparam-1} are global parameters. */
1092 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr
,
1093 PBB_TRANSFORMED_SCATTERING (pbb
));
1095 /* Extend the iteration domain with the scattering dimensions:
1096 0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}. */
1097 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1098 (&ext_domain
, PBB_DOMAIN (pbb
));
1099 ppl_insert_dimensions_pointset (ext_domain
, 0,
1100 pbb_nb_scattering_transform (pbb
)
1101 + pbb_nb_local_vars (pbb
));
1103 /* Add to sctr the extended domain. */
1104 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr
, ext_domain
);
1106 /* Extract the number of iterations. */
1107 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr
, &dim
);
1108 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
1109 ppl_set_coef (le
, time_depth
, 1);
1110 mpz_set_si (niter
, -1);
1111 ppl_max_for_le_pointset (sctr
, le
, niter
);
1113 ppl_delete_Linear_Expression (le
);
1114 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr
);
1115 ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain
);
1118 /* Translates LOOP to LST. */
1121 loop_to_lst (loop_p loop
, VEC (poly_bb_p
, heap
) *bbs
, int *i
)
1124 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1126 for (; VEC_iterate (poly_bb_p
, bbs
, *i
, pbb
); (*i
)++)
1129 basic_block bb
= GBB_BB (PBB_BLACK_BOX (pbb
));
1131 if (bb
->loop_father
== loop
)
1132 stmt
= new_lst_stmt (pbb
);
1133 else if (flow_bb_inside_loop_p (loop
, bb
))
1135 loop_p next
= loop
->inner
;
1137 while (next
&& !flow_bb_inside_loop_p (next
, bb
))
1140 stmt
= loop_to_lst (next
, bbs
, i
);
1145 return new_lst_loop (seq
);
1148 VEC_safe_push (lst_p
, heap
, seq
, stmt
);
1151 return new_lst_loop (seq
);
1154 /* Reads the original scattering of the SCOP and returns an LST
1158 scop_to_lst (scop_p scop
)
1161 int i
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
1162 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1163 sese region
= SCOP_REGION (scop
);
1165 for (i
= 0; i
< n
; i
++)
1167 poly_bb_p pbb
= VEC_index (poly_bb_p
, SCOP_BBS (scop
), i
);
1168 loop_p loop
= outermost_loop_in_sese (region
, GBB_BB (PBB_BLACK_BOX (pbb
)));
1170 if (loop_in_sese_p (loop
, region
))
1171 res
= loop_to_lst (loop
, SCOP_BBS (scop
), &i
);
1173 res
= new_lst_stmt (pbb
);
1175 VEC_safe_push (lst_p
, heap
, seq
, res
);
1178 res
= new_lst_loop (seq
);
1179 SCOP_ORIGINAL_SCHEDULE (scop
) = res
;
1180 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (res
);
1183 /* Print to FILE on a new line COLUMN white spaces. */
1186 lst_indent_to (FILE *file
, int column
)
1191 fprintf (file
, "\n#");
1193 for (i
= 0; i
< column
; i
++)
1194 fprintf (file
, " ");
1197 /* Print LST to FILE with INDENT spaces of indentation. */
1200 print_lst (FILE *file
, lst_p lst
, int indent
)
1205 lst_indent_to (file
, indent
);
1207 if (LST_LOOP_P (lst
))
1212 if (LST_LOOP_FATHER (lst
))
1213 fprintf (file
, "%d (loop", lst_dewey_number (lst
));
1215 fprintf (file
, "#(root");
1217 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1218 print_lst (file
, l
, indent
+ 2);
1220 fprintf (file
, ")");
1223 fprintf (file
, "%d stmt_%d", lst_dewey_number (lst
), pbb_index (LST_PBB (lst
)));
1226 /* Print LST to STDERR. */
1229 debug_lst (lst_p lst
)
1231 print_lst (stderr
, lst
, 0);
1234 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1237 dot_lst_1 (FILE *file
, lst_p lst
)
1242 if (LST_LOOP_P (lst
))
1247 if (!LST_LOOP_FATHER (lst
))
1248 fprintf (file
, "L -> L_%d_%d\n",
1250 lst_dewey_number (lst
));
1252 fprintf (file
, "L_%d_%d -> L_%d_%d\n",
1253 lst_depth (LST_LOOP_FATHER (lst
)),
1254 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1256 lst_dewey_number (lst
));
1258 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1259 dot_lst_1 (file
, l
);
1263 fprintf (file
, "L_%d_%d -> S_%d\n",
1264 lst_depth (LST_LOOP_FATHER (lst
)),
1265 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1266 pbb_index (LST_PBB (lst
)));
1270 /* Display the LST using dotty. */
1275 /* When debugging, enable the following code. This cannot be used
1276 in production compilers because it calls "system". */
1279 FILE *stream
= fopen ("/tmp/lst.dot", "w");
1280 gcc_assert (stream
);
1282 fputs ("digraph all {\n", stream
);
1283 dot_lst_1 (stream
, lst
);
1284 fputs ("}\n\n", stream
);
1287 x
= system ("dotty /tmp/lst.dot &");
1289 fputs ("digraph all {\n", stderr
);
1290 dot_lst_1 (stderr
, lst
);
1291 fputs ("}\n\n", stderr
);