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"
24 #include "diagnostic-core.h"
25 #include "tree-flow.h"
26 #include "tree-dump.h"
27 #include "gimple-pretty-print.h"
29 #include "tree-chrec.h"
30 #include "tree-data-ref.h"
31 #include "tree-scalar-evolution.h"
36 #include "graphite-ppl.h"
37 #include "graphite-poly.h"
38 #include "graphite-dependences.h"
39 #include "graphite-cloog-util.h"
41 #define OPENSCOP_MAX_STRING 256
43 /* Return the maximal loop depth in SCOP. */
46 scop_max_loop_depth (scop_p scop
)
52 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
54 int nb_loops
= pbb_dim_iter_domain (pbb
);
55 if (max_nb_loops
< nb_loops
)
56 max_nb_loops
= nb_loops
;
62 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
66 extend_scattering (poly_bb_p pbb
, int max_scattering
)
68 ppl_dimension_type nb_old_dims
, nb_new_dims
;
70 ppl_Coefficient_t coef
;
73 nb_added_dims
= max_scattering
- pbb_nb_scattering_transform (pbb
);
76 ppl_new_Coefficient (&coef
);
77 ppl_assign_Coefficient_from_mpz_t (coef
, one
);
79 gcc_assert (nb_added_dims
>= 0);
81 nb_old_dims
= pbb_nb_scattering_transform (pbb
) + pbb_dim_iter_domain (pbb
)
82 + scop_nb_params (PBB_SCOP (pbb
));
83 nb_new_dims
= nb_old_dims
+ nb_added_dims
;
85 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
),
86 pbb_nb_scattering_transform (pbb
), nb_added_dims
);
87 PBB_NB_SCATTERING_TRANSFORM (pbb
) += nb_added_dims
;
89 /* Add identity matrix for the added dimensions. */
90 for (i
= max_scattering
- nb_added_dims
; i
< max_scattering
; i
++)
92 ppl_Constraint_t cstr
;
93 ppl_Linear_Expression_t expr
;
95 ppl_new_Linear_Expression_with_dimension (&expr
, nb_new_dims
);
96 ppl_Linear_Expression_add_to_coefficient (expr
, i
, coef
);
97 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
98 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
99 ppl_delete_Constraint (cstr
);
100 ppl_delete_Linear_Expression (expr
);
103 ppl_delete_Coefficient (coef
);
107 /* All scattering matrices in SCOP will have the same number of scattering
111 unify_scattering_dimensions (scop_p scop
)
115 graphite_dim_t max_scattering
= 0;
117 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
118 max_scattering
= MAX (pbb_nb_scattering_transform (pbb
), max_scattering
);
120 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
121 extend_scattering (pbb
, max_scattering
);
123 return max_scattering
;
126 /* Print to FILE the pdr PH in OpenScop format. NB_SUBSCRIPTS is the number
127 of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and
128 NB_PARAMS is the number of parameters in PH. */
131 openscop_print_pdr_polyhedron (FILE *file
, ppl_const_Polyhedron_t ph
,
132 int nb_subscripts
, int alias_set_dimension
,
135 int input
, locals
, output
;
136 ppl_dimension_type alias_set_dim
= (ppl_dimension_type
) alias_set_dimension
;
137 ppl_dimension_type sub_dim_last
= alias_set_dim
+ nb_subscripts
;
138 ppl_dimension_type
*map
, i
, ph_space_dim
= sub_dim_last
+ 1;
139 ppl_Polyhedron_t pph
;
141 ppl_new_C_Polyhedron_from_C_Polyhedron (&pph
, ph
);
143 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, ph_space_dim
);
145 for (i
= 0; i
< alias_set_dim
- 1; i
++)
146 map
[i
] = nb_subscripts
+ 1 + i
;
148 for (i
= alias_set_dim
- 1; i
< sub_dim_last
; i
++)
149 map
[i
] = i
- alias_set_dim
+ 1;
151 ppl_Polyhedron_map_space_dimensions (pph
, map
, ph_space_dim
- 1);
154 input
= alias_set_dim
- nb_params
- 1;
156 /* According to OpenScop specification, the alias set column is a part of
157 the output columns. */
158 output
= nb_subscripts
+ 1;
160 openscop_print_polyhedron_matrix (file
, pph
, output
, input
, locals
, nb_params
);
163 /* Print to FILE the powerset PDR. NB_SUBSCRIPTS is the number of subscripts
164 in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and
165 NB_PARAMS is the number of parameters in PDR. */
168 openscop_print_pdr_powerset (FILE *file
,
169 ppl_Pointset_Powerset_C_Polyhedron_t ps
,
175 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it
, end
;
177 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it
);
178 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end
);
180 ppl_Pointset_Powerset_C_Polyhedron_size (ps
, &nb_disjuncts
);
181 fprintf (file
, "%d\n", (int) nb_disjuncts
);
183 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps
, it
),
184 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps
, end
);
185 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it
, end
);
186 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it
))
188 ppl_const_Polyhedron_t ph
;
190 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it
, &ph
);
191 openscop_print_pdr_polyhedron (file
, ph
, nb_subscripts
, alias_set_dim
,
195 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it
);
196 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end
);
199 /* Print to FILE the powerset PS in its OpenScop matrix form. */
202 openscop_print_powerset_matrix (FILE *file
,
203 ppl_Pointset_Powerset_C_Polyhedron_t ps
,
204 int output
, int input
, int locals
,
208 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it
, end
;
210 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it
);
211 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end
);
213 ppl_Pointset_Powerset_C_Polyhedron_size (ps
, &nb_disjuncts
);
214 fprintf (file
, "%d\n", (int) nb_disjuncts
);
216 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps
, it
),
217 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps
, end
);
218 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it
, end
);
219 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it
))
221 ppl_const_Polyhedron_t ph
;
223 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it
, &ph
);
224 openscop_print_polyhedron_matrix (file
, ph
, output
, input
, locals
,
228 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it
);
229 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end
);
232 /* Prints to FILE the scattering function of PBB in OpenScop format, at some
236 openscop_print_scattering_function_1 (FILE *file
, poly_bb_p pbb
, int verbosity
)
239 ppl_const_Polyhedron_t ph
;
243 fprintf (file
, "# scattering bb_%d (\n", pbb_index (pbb
));
244 fprintf (file
, "#eq");
246 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
247 fprintf (file
, " s%d", (int) i
);
249 for (i
= 0; i
< pbb_nb_local_vars (pbb
); i
++)
250 fprintf (file
, " lv%d", (int) i
);
252 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
253 fprintf (file
, " i%d", (int) i
);
255 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
256 fprintf (file
, " p%d", (int) i
);
258 fprintf (file
, " cst\n");
261 /* Number of disjunct components. Remove this when
262 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
263 fprintf (file
, "1\n");
265 ph
= PBB_TRANSFORMED_SCATTERING (pbb
)
266 ? PBB_TRANSFORMED_SCATTERING (pbb
)
267 : PBB_ORIGINAL_SCATTERING (pbb
);
269 openscop_print_polyhedron_matrix (file
, ph
,
270 pbb_nb_scattering_transform (pbb
),
271 pbb_dim_iter_domain (pbb
),
272 pbb_nb_local_vars (pbb
),
273 pbb_nb_params (pbb
));
276 fprintf (file
, "#)\n");
279 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
283 print_scattering_function_1 (FILE *file
, poly_bb_p pbb
, int verbosity
)
289 fprintf (file
, "# scattering bb_%d (\n", pbb_index (pbb
));
290 fprintf (file
, "#eq");
292 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
293 fprintf (file
, " s%d", (int) i
);
295 for (i
= 0; i
< pbb_nb_local_vars (pbb
); i
++)
296 fprintf (file
, " lv%d", (int) i
);
298 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
299 fprintf (file
, " i%d", (int) i
);
301 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
302 fprintf (file
, " p%d", (int) i
);
304 fprintf (file
, " cst\n");
307 /* Number of disjunct components. Remove this when
308 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
309 fprintf (file
, "1\n");
310 ppl_print_polyhedron_matrix (file
, PBB_TRANSFORMED_SCATTERING (pbb
)
311 ? PBB_TRANSFORMED_SCATTERING (pbb
)
312 : PBB_ORIGINAL_SCATTERING (pbb
));
315 fprintf (file
, "#)\n");
318 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
322 print_scattering_function (FILE *file
, poly_bb_p pbb
, int verbosity
)
324 if (!PBB_TRANSFORMED (pbb
))
327 if (PBB_TRANSFORMED_SCATTERING (pbb
)
328 || PBB_ORIGINAL_SCATTERING (pbb
))
331 fprintf (file
, "# Scattering function is provided\n");
333 fprintf (file
, "1\n");
338 fprintf (file
, "# Scattering function is not provided\n");
340 fprintf (file
, "0\n");
344 openscop_print_scattering_function_1 (file
, pbb
, verbosity
);
347 fprintf (file
, "# Scattering names are not provided\n");
349 fprintf (file
, "0\n");
353 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
357 print_iteration_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
359 print_pbb_domain (file
, pbb
, verbosity
);
362 /* Prints to FILE the scattering functions of every PBB of SCOP. */
365 print_scattering_functions (FILE *file
, scop_p scop
, int verbosity
)
370 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
371 print_scattering_function (file
, pbb
, verbosity
);
374 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
378 print_iteration_domains (FILE *file
, scop_p scop
, int verbosity
)
383 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
384 print_iteration_domain (file
, pbb
, verbosity
);
387 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
391 debug_scattering_function (poly_bb_p pbb
, int verbosity
)
393 print_scattering_function (stderr
, pbb
, verbosity
);
396 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
400 debug_iteration_domain (poly_bb_p pbb
, int verbosity
)
402 print_iteration_domain (stderr
, pbb
, verbosity
);
405 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
406 some VERBOSITY level. */
409 debug_scattering_functions (scop_p scop
, int verbosity
)
411 print_scattering_functions (stderr
, scop
, verbosity
);
414 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
415 some VERBOSITY level. */
418 debug_iteration_domains (scop_p scop
, int verbosity
)
420 print_iteration_domains (stderr
, scop
, verbosity
);
423 /* Read N integer from FILE. */
426 openscop_read_N_int (FILE *file
, int N
)
428 char s
[OPENSCOP_MAX_STRING
];
430 int i
, *res
= (int *) xmalloc (OPENSCOP_MAX_STRING
* sizeof (int));
432 /* Skip blank and commented lines. */
433 while (fgets (s
, sizeof s
, file
) == (char *) 0
440 for (i
= 0; i
< N
; i
++)
442 sscanf (str
, "%d", &res
[i
]);
444 /* Jump the integer that was read. */
445 while ((*str
) && !ISSPACE (*str
) && (*str
!= '#'))
449 while ((*str
) && ISSPACE (*str
) && (*str
!= '#'))
456 /* Read one integer from FILE. */
459 openscop_read_one_int (FILE *file
)
461 int *x
= openscop_read_N_int (file
, 1);
468 /* Read N string from FILE. */
471 openscop_read_N_string (FILE *file
, int N
)
474 char str
[OPENSCOP_MAX_STRING
];
475 char *tmp
= (char *) xmalloc (sizeof (char) * OPENSCOP_MAX_STRING
);
478 /* Skip blank and commented lines. */
479 while (fgets (str
, sizeof str
, file
) == (char *) 0
487 for (i
= 0; i
< N
; i
++)
489 /* Read the first word. */
490 for (; (*s
) && (!ISSPACE (*s
)) && (*s
!= '#'); ++count
)
497 while ((*s
) && ISSPACE (*s
) && (*s
!= '#'))
506 /* Read one string from FILE. */
509 openscop_read_one_string (FILE *file
)
511 return openscop_read_N_string (file
, 1);
514 /* Read from FILE the powerset PS in its OpenScop matrix form. OUTPUT is the
515 number of output dimensions, INPUT is the number of input dimensions,
516 LOCALS is the number of existentially quantified variables and PARAMS is
517 the number of parameters. */
520 openscop_read_powerset_matrix (FILE *file
,
521 ppl_Pointset_Powerset_C_Polyhedron_t
*ps
,
522 int *output
, int *input
, int *locals
,
527 nb_disjuncts
= openscop_read_one_int (file
);
529 for (i
= 0; i
< nb_disjuncts
; i
++)
533 openscop_read_polyhedron_matrix (file
, &ph
, output
, input
, locals
,
538 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (ps
, ph
);
540 ppl_Pointset_Powerset_C_Polyhedron_add_disjunct (*ps
, ph
);
544 /* Read a scattering function from FILE and save it to PBB. Return whether
545 the scattering function was provided or not. */
548 graphite_read_scatt (FILE *file
, poly_bb_p pbb
)
550 bool scattering_provided
= false;
551 int output
, input
, locals
, params
;
552 ppl_Polyhedron_t newp
;
554 if (openscop_read_one_int (file
) > 0)
556 /* Read number of disjunct components. */
557 openscop_read_one_int (file
);
559 /* Read scattering function. */
560 openscop_read_polyhedron_matrix (file
, &newp
, &output
, &input
,
562 store_scattering (PBB_SCOP (pbb
));
563 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
564 PBB_TRANSFORMED_SCATTERING (pbb
) = newp
;
565 PBB_NB_LOCAL_VARIABLES (pbb
) = locals
;
567 /* New scattering dimension. */
568 PBB_NB_SCATTERING_TRANSFORM (pbb
) = output
;
570 scattering_provided
= true;
573 return scattering_provided
;
576 /* Read a scop file. Return true if the scop is transformed. */
579 graphite_read_scop_file (FILE *file
, scop_p scop
)
581 char *tmp
, *language
;
582 size_t i
, j
, nb_statements
, nbr
, nbw
;
583 int input
, output
, locals
, params
;
584 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
586 bool transform_done
= false;
588 /* Ensure that the file is in OpenScop format. */
589 tmp
= openscop_read_N_string (file
, 2);
591 if (strcmp (tmp
, "SCoP 1"))
593 error ("the file is not in OpenScop format");
599 /* Read the language. */
600 language
= openscop_read_one_string (file
);
602 if (strcmp (language
, "Gimple"))
604 error ("the language is not recognized");
610 /* Read the context but do not use it. */
611 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
, ¶ms
);
613 if ((size_t) params
!= scop
->nb_params
)
615 error ("parameters number in the scop file is different from the"
616 " internal scop parameter number");
620 /* Read parameter names if provided. */
621 if (openscop_read_one_int (file
))
622 openscop_read_N_string (file
, scop
->nb_params
);
624 nb_statements
= openscop_read_one_int (file
);
626 if (nb_statements
!= VEC_length (poly_bb_p
, SCOP_BBS (scop
)))
628 error ("number of statements in the OpenScop file does not match"
629 " the graphite internal statements number");
633 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
635 /* Read iteration domain. */
636 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
,
639 /* Read scattering. */
640 transform_done
= graphite_read_scatt (file
, pbb
);
642 /* Scattering names. */
643 openscop_read_one_int (file
);
645 /* Read access functions. */
646 if (openscop_read_one_int (file
) > 0)
648 nbr
= openscop_read_one_int (file
);
650 /* Read access functions. */
651 for (j
= 0; j
< nbr
; j
++)
652 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
,
655 nbw
= openscop_read_one_int (file
);
657 /* Write access functions. */
658 for (j
= 0; j
< nbw
; j
++)
659 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
,
663 /* Statement body. */
664 openscop_read_one_int (file
);
667 return transform_done
;
670 /* Initialize and return a file that will be used to write a scop. SCOP_NUMBER
671 is a sequential number (identifier) used to differentiate scop files.
672 Examples of the generated file names: dump_base_name.0.graphite,
673 dump_base_name.1.graphite, dump_base_name.2.graphite, etc. */
676 init_graphite_out_file (int scop_number
)
678 FILE *graphite_out_file
;
679 int len
= strlen (dump_base_name
);
680 char *dumpname
= XNEWVEC (char, len
+ 25);
681 char *s_scop_number
= XNEWVEC (char, 15);
683 memcpy (dumpname
, dump_base_name
, len
+ 1);
684 strip_off_ending (dumpname
, len
);
685 sprintf (s_scop_number
, ".%d", scop_number
);
686 strcat (dumpname
, s_scop_number
);
687 strcat (dumpname
, ".graphite");
688 graphite_out_file
= fopen (dumpname
, "w+b");
690 if (graphite_out_file
== 0)
691 fatal_error ("can%'t open %s for writing: %m", dumpname
);
695 return graphite_out_file
;
698 /* Open and return a file used for scop reading. SCOP_NUMBER is a sequential
699 number (identifier) used to differentiate scop files. Examples of the
700 generated file names: dump_base_name.0.graphite, dump_base_name.1.graphite,
701 dump_base_name.2.graphite, etc. */
704 init_graphite_in_file (int scop_number
)
706 FILE *graphite_in_file
;
707 int len
= strlen (dump_base_name
);
708 char *dumpname
= XNEWVEC (char, len
+ 25);
709 char *s_scop_number
= XNEWVEC (char, 15);
711 memcpy (dumpname
, dump_base_name
, len
+ 1);
712 strip_off_ending (dumpname
, len
);
713 sprintf (s_scop_number
, ".%d", scop_number
);
714 strcat (dumpname
, s_scop_number
);
715 strcat (dumpname
, ".graphite");
716 graphite_in_file
= fopen (dumpname
, "r+b");
718 if (graphite_in_file
== 0)
719 fatal_error ("can%'t open %s for reading: %m", dumpname
);
723 return graphite_in_file
;
726 /* Apply graphite transformations to all the basic blocks of SCOP. */
729 apply_poly_transforms (scop_p scop
)
731 bool transform_done
= false;
733 static size_t file_scop_number
= 0;
735 /* This feature is only enabled in the Graphite branch. */
738 graphite_file
= init_graphite_in_file (file_scop_number
);
739 transform_done
|= graphite_read_scop_file (graphite_file
, scop
);
741 if (!graphite_legal_transform (scop
))
742 fatal_error ("the graphite file read for scop %d does not contain a legal transform",
743 (int) file_scop_number
);
748 /* Generate code even if we did not apply any real transformation.
749 This also allows to check the performance for the identity
750 transformation: GIMPLE -> GRAPHITE -> GIMPLE
751 Keep in mind that CLooG optimizes in control, so the loop structure
752 may change, even if we only use -fgraphite-identity. */
753 if (flag_graphite_identity
)
754 transform_done
= true;
756 if (flag_loop_parallelize_all
)
757 transform_done
= true;
760 transform_done
|= scop_do_block (scop
);
763 if (flag_loop_strip_mine
)
764 transform_done
|= scop_do_strip_mine (scop
, 0);
766 if (flag_loop_interchange
)
767 transform_done
|= scop_do_interchange (scop
);
770 if (flag_loop_flatten
)
771 transform_done
|= flatten_all_loops (scop
);
773 /* This feature is only enabled in the Graphite branch. */
776 graphite_file
= init_graphite_out_file (file_scop_number
);
777 print_scop (graphite_file
, scop
, 1);
781 return transform_done
;
784 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
785 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */
788 can_collapse_pdrs (poly_dr_p pdr1
, poly_dr_p pdr2
)
791 ppl_Pointset_Powerset_C_Polyhedron_t af1
, af2
, diff
;
793 if (PDR_PBB (pdr1
) != PDR_PBB (pdr2
)
794 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
)
795 || PDR_TYPE (pdr1
) != PDR_TYPE (pdr2
))
798 af1
= PDR_ACCESSES (pdr1
);
799 af2
= PDR_ACCESSES (pdr2
);
800 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
802 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff
, af2
);
804 res
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff
);
805 ppl_delete_Pointset_Powerset_C_Polyhedron (diff
);
809 /* Removes duplicated data references in PBB. */
812 pbb_remove_duplicate_pdrs (poly_bb_p pbb
)
815 poly_dr_p pdr1
, pdr2
;
816 unsigned n
= VEC_length (poly_dr_p
, PBB_DRS (pbb
));
817 VEC (poly_dr_p
, heap
) *collapsed
= VEC_alloc (poly_dr_p
, heap
, n
);
819 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr1
)
820 FOR_EACH_VEC_ELT (poly_dr_p
, collapsed
, j
, pdr2
)
821 if (!can_collapse_pdrs (pdr1
, pdr2
))
822 VEC_quick_push (poly_dr_p
, collapsed
, pdr1
);
824 VEC_free (poly_dr_p
, heap
, collapsed
);
825 PBB_PDR_DUPLICATES_REMOVED (pbb
) = true;
828 /* Create a new polyhedral data reference and add it to PBB. It is
829 defined by its ACCESSES, its TYPE, and the number of subscripts
833 new_poly_dr (poly_bb_p pbb
, int dr_base_object_set
,
834 ppl_Pointset_Powerset_C_Polyhedron_t accesses
,
835 enum poly_dr_type type
, void *cdr
, graphite_dim_t nb_subscripts
)
838 poly_dr_p pdr
= XNEW (struct poly_dr
);
841 PDR_BASE_OBJECT_SET (pdr
) = dr_base_object_set
;
842 PDR_NB_REFS (pdr
) = 1;
844 PDR_ACCESSES (pdr
) = accesses
;
845 PDR_TYPE (pdr
) = type
;
847 PDR_NB_SUBSCRIPTS (pdr
) = nb_subscripts
;
848 VEC_safe_push (poly_dr_p
, heap
, PBB_DRS (pbb
), pdr
);
851 /* Free polyhedral data reference PDR. */
854 free_poly_dr (poly_dr_p pdr
)
856 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr
));
860 /* Create a new polyhedral black box. */
863 new_poly_bb (scop_p scop
, void *black_box
)
865 poly_bb_p pbb
= XNEW (struct poly_bb
);
867 PBB_DOMAIN (pbb
) = NULL
;
868 PBB_SCOP (pbb
) = scop
;
869 pbb_set_black_box (pbb
, black_box
);
870 PBB_TRANSFORMED (pbb
) = NULL
;
871 PBB_SAVED (pbb
) = NULL
;
872 PBB_ORIGINAL (pbb
) = NULL
;
873 PBB_DRS (pbb
) = VEC_alloc (poly_dr_p
, heap
, 3);
874 PBB_IS_REDUCTION (pbb
) = false;
875 PBB_PDR_DUPLICATES_REMOVED (pbb
) = false;
876 GBB_PBB ((gimple_bb_p
) black_box
) = pbb
;
881 /* Free polyhedral black box. */
884 free_poly_bb (poly_bb_p pbb
)
889 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb
));
891 if (PBB_TRANSFORMED (pbb
))
892 poly_scattering_free (PBB_TRANSFORMED (pbb
));
895 poly_scattering_free (PBB_SAVED (pbb
));
897 if (PBB_ORIGINAL (pbb
))
898 poly_scattering_free (PBB_ORIGINAL (pbb
));
901 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
)
904 VEC_free (poly_dr_p
, heap
, PBB_DRS (pbb
));
909 print_pdr_access_layout (FILE *file
, poly_bb_p pbb
, poly_dr_p pdr
)
913 fprintf (file
, "# eq");
915 fprintf (file
, " alias");
917 for (i
= 0; i
< PDR_NB_SUBSCRIPTS (pdr
); i
++)
918 fprintf (file
, " sub%d", (int) i
);
920 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
921 fprintf (file
, " i%d", (int) i
);
923 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
924 fprintf (file
, " p%d", (int) i
);
926 fprintf (file
, " cst\n");
929 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
933 print_pdr (FILE *file
, poly_dr_p pdr
, int verbosity
)
939 fprintf (file
, "# pdr_%d (", PDR_ID (pdr
));
941 switch (PDR_TYPE (pdr
))
944 fprintf (file
, "read \n");
948 fprintf (file
, "write \n");
952 fprintf (file
, "may_write \n");
959 dump_data_reference (file
, (data_reference_p
) PDR_CDR (pdr
));
964 fprintf (file
, "# data accesses (\n");
965 print_pdr_access_layout (file
, PDR_PBB (pdr
), pdr
);
968 alias_set_dim
= pdr_alias_set_dim (pdr
) + 1;
970 openscop_print_pdr_powerset (file
,
972 PDR_NB_SUBSCRIPTS (pdr
),
974 pbb_nb_params (PDR_PBB (pdr
)));
977 fprintf (file
, "#)\n");
980 fprintf (file
, "#)\n");
983 /* Prints to STDERR the polyhedral data reference PDR, at some
987 debug_pdr (poly_dr_p pdr
, int verbosity
)
989 print_pdr (stderr
, pdr
, verbosity
);
992 /* Creates a new SCOP containing REGION. */
995 new_scop (void *region
)
997 scop_p scop
= XNEW (struct scop
);
999 SCOP_CONTEXT (scop
) = NULL
;
1000 scop_set_region (scop
, region
);
1001 SCOP_BBS (scop
) = VEC_alloc (poly_bb_p
, heap
, 3);
1002 SCOP_ORIGINAL_PDDRS (scop
) = htab_create (10, hash_poly_ddr_p
,
1003 eq_poly_ddr_p
, free_poly_ddr
);
1004 SCOP_ORIGINAL_SCHEDULE (scop
) = NULL
;
1005 SCOP_TRANSFORMED_SCHEDULE (scop
) = NULL
;
1006 SCOP_SAVED_SCHEDULE (scop
) = NULL
;
1007 POLY_SCOP_P (scop
) = false;
1015 free_scop (scop_p scop
)
1020 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1023 VEC_free (poly_bb_p
, heap
, SCOP_BBS (scop
));
1025 if (SCOP_CONTEXT (scop
))
1026 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop
));
1028 htab_delete (SCOP_ORIGINAL_PDDRS (scop
));
1029 free_lst (SCOP_ORIGINAL_SCHEDULE (scop
));
1030 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1031 free_lst (SCOP_SAVED_SCHEDULE (scop
));
1035 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
1039 openscop_print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
1042 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1044 if (!PBB_DOMAIN (pbb
))
1049 fprintf (file
, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
1050 fprintf (file
, "#eq");
1052 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
1053 fprintf (file
, " i%d", (int) i
);
1055 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
1056 fprintf (file
, " p%d", (int) i
);
1058 fprintf (file
, " cst\n");
1061 if (PBB_DOMAIN (pbb
))
1062 openscop_print_powerset_matrix (file
, PBB_DOMAIN (pbb
),
1063 pbb_dim_iter_domain (pbb
),
1066 pbb_nb_params (pbb
));
1068 fprintf (file
, "0\n");
1071 fprintf (file
, "#)\n");
1074 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
1077 print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
1080 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1082 if (!PBB_DOMAIN (pbb
))
1087 fprintf (file
, "# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
1088 fprintf (file
, "# eq");
1090 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
1091 fprintf (file
, " i%d", (int) i
);
1093 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
1094 fprintf (file
, " p%d", (int) i
);
1096 fprintf (file
, " cst\n");
1099 if (PBB_DOMAIN (pbb
))
1100 ppl_print_powerset_matrix (file
, PBB_DOMAIN (pbb
));
1102 fprintf (file
, "0\n");
1105 fprintf (file
, "#)\n");
1108 /* Dump the cases of a graphite basic block GBB on FILE. */
1111 dump_gbb_cases (FILE *file
, gimple_bb_p gbb
)
1115 VEC (gimple
, heap
) *cases
;
1120 cases
= GBB_CONDITION_CASES (gbb
);
1121 if (VEC_empty (gimple
, cases
))
1124 fprintf (file
, "# cases bb_%d (\n", GBB_BB (gbb
)->index
);
1126 FOR_EACH_VEC_ELT (gimple
, cases
, i
, stmt
)
1128 fprintf (file
, "# ");
1129 print_gimple_stmt (file
, stmt
, 0, 0);
1132 fprintf (file
, "#)\n");
1135 /* Dump conditions of a graphite basic block GBB on FILE. */
1138 dump_gbb_conditions (FILE *file
, gimple_bb_p gbb
)
1142 VEC (gimple
, heap
) *conditions
;
1147 conditions
= GBB_CONDITIONS (gbb
);
1148 if (VEC_empty (gimple
, conditions
))
1151 fprintf (file
, "# conditions bb_%d (\n", GBB_BB (gbb
)->index
);
1153 FOR_EACH_VEC_ELT (gimple
, conditions
, i
, stmt
)
1155 fprintf (file
, "# ");
1156 print_gimple_stmt (file
, stmt
, 0, 0);
1159 fprintf (file
, "#)\n");
1162 /* Print to FILE all the data references of PBB, at some VERBOSITY
1166 print_pdrs (FILE *file
, poly_bb_p pbb
, int verbosity
)
1173 if (VEC_length (poly_dr_p
, PBB_DRS (pbb
)) == 0)
1176 fprintf (file
, "# Access informations are not provided\n");\
1177 fprintf (file
, "0\n");
1182 fprintf (file
, "# Data references (\n");
1185 fprintf (file
, "# Access informations are provided\n");
1186 fprintf (file
, "1\n");
1188 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
)
1189 if (PDR_TYPE (pdr
) == PDR_READ
)
1195 fprintf (file
, "# Read data references (\n");
1198 fprintf (file
, "# Read access informations\n");
1199 fprintf (file
, "%d\n", nb_reads
);
1201 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
)
1202 if (PDR_TYPE (pdr
) == PDR_READ
)
1203 print_pdr (file
, pdr
, verbosity
);
1206 fprintf (file
, "#)\n");
1209 fprintf (file
, "# Write data references (\n");
1212 fprintf (file
, "# Write access informations\n");
1213 fprintf (file
, "%d\n", nb_writes
);
1215 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
)
1216 if (PDR_TYPE (pdr
) != PDR_READ
)
1217 print_pdr (file
, pdr
, verbosity
);
1220 fprintf (file
, "#)\n");
1223 fprintf (file
, "#)\n");
1226 /* Print to STDERR all the data references of PBB. */
1229 debug_pdrs (poly_bb_p pbb
, int verbosity
)
1231 print_pdrs (stderr
, pbb
, verbosity
);
1234 /* Print to FILE the body of PBB, at some VERBOSITY level.
1235 If statement_body_provided is false statement body is not printed. */
1238 print_pbb_body (FILE *file
, poly_bb_p pbb
, int verbosity
,
1239 bool statement_body_provided
)
1242 fprintf (file
, "# Body (\n");
1244 if (!statement_body_provided
)
1247 fprintf (file
, "# Statement body is not provided\n");
1249 fprintf (file
, "0\n");
1252 fprintf (file
, "#)\n");
1257 fprintf (file
, "# Statement body is provided\n");
1258 fprintf (file
, "1\n");
1261 fprintf (file
, "# Original iterator names\n# Iterator names are not provided yet.\n");
1264 fprintf (file
, "# Statement body\n");
1266 fprintf (file
, "{\n");
1267 dump_bb (pbb_bb (pbb
), file
, 0);
1268 fprintf (file
, "}\n");
1271 fprintf (file
, "#)\n");
1274 /* Print to FILE the domain and scattering function of PBB, at some
1278 print_pbb (FILE *file
, poly_bb_p pbb
, int verbosity
)
1282 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1283 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
1284 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
1287 openscop_print_pbb_domain (file
, pbb
, verbosity
);
1288 print_scattering_function (file
, pbb
, verbosity
);
1289 print_pdrs (file
, pbb
, verbosity
);
1290 print_pbb_body (file
, pbb
, verbosity
, false);
1293 fprintf (file
, "#)\n");
1296 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
1299 print_scop_params (FILE *file
, scop_p scop
, int verbosity
)
1305 fprintf (file
, "# parameters (\n");
1307 if (VEC_length (tree
, SESE_PARAMS (SCOP_REGION (scop
))))
1310 fprintf (file
, "# Parameter names are provided\n");
1312 fprintf (file
, "1\n");
1315 fprintf (file
, "# Parameter names\n");
1320 fprintf (file
, "# Parameter names are not provided\n");
1321 fprintf (file
, "0\n");
1324 FOR_EACH_VEC_ELT (tree
, SESE_PARAMS (SCOP_REGION (scop
)), i
, t
)
1326 print_generic_expr (file
, t
, 0);
1327 fprintf (file
, " ");
1330 fprintf (file
, "\n");
1333 fprintf (file
, "#)\n");
1336 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1340 openscop_print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
1346 fprintf (file
, "# Context (\n");
1347 fprintf (file
, "#eq");
1349 for (i
= 0; i
< scop_nb_params (scop
); i
++)
1350 fprintf (file
, " p%d", (int) i
);
1352 fprintf (file
, " cst\n");
1355 if (SCOP_CONTEXT (scop
))
1356 openscop_print_powerset_matrix (file
, SCOP_CONTEXT (scop
), 0, 0, 0,
1357 scop_nb_params (scop
));
1359 fprintf (file
, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop
) + 2,
1360 (int) scop_nb_params (scop
));
1363 fprintf (file
, "# )\n");
1366 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
1369 print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
1375 fprintf (file
, "# Context (\n");
1376 fprintf (file
, "#eq");
1378 for (i
= 0; i
< scop_nb_params (scop
); i
++)
1379 fprintf (file
, " p%d", (int) i
);
1381 fprintf (file
, " cst\n");
1384 if (SCOP_CONTEXT (scop
))
1385 ppl_print_powerset_matrix (file
, SCOP_CONTEXT (scop
));
1387 fprintf (file
, "0 %d\n", (int) scop_nb_params (scop
) + 2);
1390 fprintf (file
, "# )\n");
1393 /* Print to FILE the SCOP, at some VERBOSITY level. */
1396 print_scop (FILE *file
, scop_p scop
, int verbosity
)
1401 fprintf (file
, "SCoP 1\n#(\n");
1402 fprintf (file
, "# Language\nGimple\n");
1403 openscop_print_scop_context (file
, scop
, verbosity
);
1404 print_scop_params (file
, scop
, verbosity
);
1407 fprintf (file
, "# Number of statements\n");
1409 fprintf (file
, "%d\n",VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1411 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1412 print_pbb (file
, pbb
, verbosity
);
1416 fprintf (file
, "# original_lst (\n");
1417 print_lst (file
, SCOP_ORIGINAL_SCHEDULE (scop
), 0);
1418 fprintf (file
, "\n#)\n");
1420 fprintf (file
, "# transformed_lst (\n");
1421 print_lst (file
, SCOP_TRANSFORMED_SCHEDULE (scop
), 0);
1422 fprintf (file
, "\n#)\n");
1425 fprintf (file
, "#)\n");
1428 /* Print to FILE the input file that CLooG would expect as input, at
1429 some VERBOSITY level. */
1432 print_cloog (FILE *file
, scop_p scop
, int verbosity
)
1437 fprintf (file
, "# SCoP (generated by GCC/Graphite\n");
1439 fprintf (file
, "# CLooG output language\n");
1440 fprintf (file
, "c\n");
1442 print_scop_context (file
, scop
, verbosity
);
1443 print_scop_params (file
, scop
, verbosity
);
1446 fprintf (file
, "# Number of statements\n");
1448 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1450 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1453 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1455 print_pbb_domain (file
, pbb
, verbosity
);
1456 fprintf (file
, "0 0 0");
1459 fprintf (file
, "# For future CLooG options.\n");
1461 fprintf (file
, "\n");
1464 fprintf (file
, "#)\n");
1467 fprintf (file
, "0");
1469 fprintf (file
, "# Don't set the iterator names.\n");
1471 fprintf (file
, "\n");
1474 fprintf (file
, "# Number of scattering functions\n");
1476 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1477 unify_scattering_dimensions (scop
);
1479 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1481 if (!PBB_TRANSFORMED (pbb
)
1482 || !(PBB_TRANSFORMED_SCATTERING (pbb
)
1483 || PBB_ORIGINAL_SCATTERING (pbb
)))
1487 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1489 print_scattering_function_1 (file
, pbb
, verbosity
);
1492 fprintf (file
, "#)\n");
1495 fprintf (file
, "0");
1497 fprintf (file
, "# Don't set the scattering dimension names.\n");
1499 fprintf (file
, "\n");
1501 fprintf (file
, "#)\n");
1504 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
1507 debug_pbb_domain (poly_bb_p pbb
, int verbosity
)
1509 print_pbb_domain (stderr
, pbb
, verbosity
);
1512 /* Print to FILE the domain and scattering function of PBB, at some
1516 debug_pbb (poly_bb_p pbb
, int verbosity
)
1518 print_pbb (stderr
, pbb
, verbosity
);
1521 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
1524 debug_scop_context (scop_p scop
, int verbosity
)
1526 print_scop_context (stderr
, scop
, verbosity
);
1529 /* Print to STDERR the SCOP, at some VERBOSITY level. */
1532 debug_scop (scop_p scop
, int verbosity
)
1534 print_scop (stderr
, scop
, verbosity
);
1537 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1541 debug_cloog (scop_p scop
, int verbosity
)
1543 print_cloog (stderr
, scop
, verbosity
);
1546 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1550 debug_scop_params (scop_p scop
, int verbosity
)
1552 print_scop_params (stderr
, scop
, verbosity
);
1556 /* The dimension in the transformed scattering polyhedron of PBB
1557 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
1560 psct_scattering_dim_for_loop_depth (poly_bb_p pbb
, graphite_dim_t loop_depth
)
1562 ppl_const_Constraint_System_t pcs
;
1563 ppl_Constraint_System_const_iterator_t cit
, cend
;
1564 ppl_const_Constraint_t cstr
;
1565 ppl_Polyhedron_t ph
= PBB_TRANSFORMED_SCATTERING (pbb
);
1566 ppl_dimension_type iter
= psct_iterator_dim (pbb
, loop_depth
);
1567 ppl_Linear_Expression_t expr
;
1568 ppl_Coefficient_t coef
;
1573 ppl_new_Coefficient (&coef
);
1574 ppl_Polyhedron_get_constraints (ph
, &pcs
);
1575 ppl_new_Constraint_System_const_iterator (&cit
);
1576 ppl_new_Constraint_System_const_iterator (&cend
);
1578 for (ppl_Constraint_System_begin (pcs
, cit
),
1579 ppl_Constraint_System_end (pcs
, cend
);
1580 !ppl_Constraint_System_const_iterator_equal_test (cit
, cend
);
1581 ppl_Constraint_System_const_iterator_increment (cit
))
1583 ppl_Constraint_System_const_iterator_dereference (cit
, &cstr
);
1584 ppl_new_Linear_Expression_from_Constraint (&expr
, cstr
);
1585 ppl_Linear_Expression_coefficient (expr
, iter
, coef
);
1586 ppl_Coefficient_to_mpz_t (coef
, val
);
1588 if (mpz_sgn (val
) == 0)
1590 ppl_delete_Linear_Expression (expr
);
1594 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
1596 ppl_dimension_type scatter
= psct_scattering_dim (pbb
, i
);
1598 ppl_Linear_Expression_coefficient (expr
, scatter
, coef
);
1599 ppl_Coefficient_to_mpz_t (coef
, val
);
1601 if (mpz_sgn (val
) != 0)
1604 ppl_delete_Linear_Expression (expr
);
1605 ppl_delete_Coefficient (coef
);
1606 ppl_delete_Constraint_System_const_iterator (cit
);
1607 ppl_delete_Constraint_System_const_iterator (cend
);
1617 /* Returns the number of iterations RES of the loop around PBB at
1618 time(scattering) dimension TIME_DEPTH. */
1621 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
1622 graphite_dim_t time_depth
,
1625 ppl_Pointset_Powerset_C_Polyhedron_t domain
, sctr_lb
, sctr_ub
;
1626 ppl_dimension_type domain_dim
, sctr_dim
;
1627 graphite_dim_t dim_iter_domain
= pbb_dim_iter_domain (pbb
);
1628 ppl_Linear_Expression_t le
;
1629 mpz_t lb
, ub
, diff
, one
;
1632 ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb
), &sctr_dim
);
1634 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1635 (&domain
, PBB_DOMAIN (pbb
));
1637 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain
, &domain_dim
);
1643 mpz_set_si (one
, 1);
1645 /* Compute the upper bound on the original iteration domain and add
1646 that upper bound to the scattering. */
1647 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1648 (&sctr_ub
, PBB_TRANSFORMED_SCATTERING (pbb
));
1649 for (i
= 0; i
< (int) dim_iter_domain
; i
++)
1651 ppl_Linear_Expression_t eq
;
1652 ppl_Constraint_t pc
;
1653 ppl_Constraint_System_t cs
;
1654 ppl_Polyhedron_t ph
;
1655 ppl_Pointset_Powerset_C_Polyhedron_t pph
;
1657 ppl_new_Linear_Expression_with_dimension (&le
, domain_dim
);
1658 ppl_set_coef (le
, i
, 1);
1659 ppl_min_for_le_pointset (domain
, le
, lb
);
1660 ppl_max_for_le_pointset (domain
, le
, ub
);
1661 mpz_sub (diff
, ub
, lb
);
1662 mpz_add (diff
, diff
, one
);
1664 ppl_new_Linear_Expression_with_dimension (&eq
, sctr_dim
);
1665 ppl_set_coef (eq
, psct_iterator_dim (pbb
, i
), -1);
1666 ppl_set_inhomogeneous_gmp (eq
, diff
);
1668 ppl_new_Constraint (&pc
, eq
, PPL_CONSTRAINT_TYPE_EQUAL
);
1669 ppl_new_Constraint_System_from_Constraint (&cs
, pc
);
1670 ppl_new_C_Polyhedron_from_Constraint_System (&ph
, cs
);
1671 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph
, ph
);
1672 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub
, pph
);
1674 ppl_delete_Linear_Expression (le
);
1675 ppl_delete_Linear_Expression (eq
);
1676 ppl_delete_Polyhedron (ph
);
1677 ppl_delete_Pointset_Powerset_C_Polyhedron (pph
);
1678 ppl_delete_Constraint (pc
);
1679 ppl_delete_Constraint_System (cs
);
1682 /* Compute the lower bound on the original iteration domain and add
1683 it to the scattering. */
1684 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1685 (&sctr_lb
, PBB_TRANSFORMED_SCATTERING (pbb
));
1686 for (i
= 0; i
< (int) dim_iter_domain
; i
++)
1688 ppl_Linear_Expression_t eq
;
1689 ppl_Constraint_t pc
;
1690 ppl_Constraint_System_t cs
;
1691 ppl_Polyhedron_t ph
;
1692 ppl_Pointset_Powerset_C_Polyhedron_t pph
;
1694 ppl_new_Linear_Expression_with_dimension (&le
, domain_dim
);
1695 ppl_set_coef (le
, i
, 1);
1696 ppl_min_for_le_pointset (domain
, le
, lb
);
1698 ppl_new_Linear_Expression_with_dimension (&eq
, sctr_dim
);
1699 ppl_set_coef (eq
, psct_iterator_dim (pbb
, i
), -1);
1700 ppl_set_inhomogeneous_gmp (eq
, lb
);
1702 ppl_new_Constraint (&pc
, eq
, PPL_CONSTRAINT_TYPE_EQUAL
);
1703 ppl_new_Constraint_System_from_Constraint (&cs
, pc
);
1704 ppl_new_C_Polyhedron_from_Constraint_System (&ph
, cs
);
1705 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph
, ph
);
1706 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb
, pph
);
1708 ppl_delete_Linear_Expression (le
);
1709 ppl_delete_Linear_Expression (eq
);
1710 ppl_delete_Polyhedron (ph
);
1711 ppl_delete_Pointset_Powerset_C_Polyhedron (pph
);
1712 ppl_delete_Constraint (pc
);
1713 ppl_delete_Constraint_System (cs
);
1716 /* Extract the number of iterations. */
1717 ppl_new_Linear_Expression_with_dimension (&le
, sctr_dim
);
1718 ppl_set_coef (le
, time_depth
, 1);
1719 ppl_min_for_le_pointset (sctr_lb
, le
, lb
);
1720 ppl_max_for_le_pointset (sctr_ub
, le
, ub
);
1721 mpz_sub (res
, ub
, lb
);
1727 ppl_delete_Linear_Expression (le
);
1728 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub
);
1729 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb
);
1730 ppl_delete_Pointset_Powerset_C_Polyhedron (domain
);
1733 /* Translates LOOP to LST. */
1736 loop_to_lst (loop_p loop
, VEC (poly_bb_p
, heap
) *bbs
, int *i
)
1739 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1741 for (; VEC_iterate (poly_bb_p
, bbs
, *i
, pbb
); (*i
)++)
1744 basic_block bb
= GBB_BB (PBB_BLACK_BOX (pbb
));
1746 if (bb
->loop_father
== loop
)
1747 stmt
= new_lst_stmt (pbb
);
1748 else if (flow_bb_inside_loop_p (loop
, bb
))
1750 loop_p next
= loop
->inner
;
1752 while (next
&& !flow_bb_inside_loop_p (next
, bb
))
1755 stmt
= loop_to_lst (next
, bbs
, i
);
1760 return new_lst_loop (seq
);
1763 VEC_safe_push (lst_p
, heap
, seq
, stmt
);
1766 return new_lst_loop (seq
);
1769 /* Reads the original scattering of the SCOP and returns an LST
1773 scop_to_lst (scop_p scop
)
1776 int i
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
1777 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1778 sese region
= SCOP_REGION (scop
);
1780 for (i
= 0; i
< n
; i
++)
1782 poly_bb_p pbb
= VEC_index (poly_bb_p
, SCOP_BBS (scop
), i
);
1783 loop_p loop
= outermost_loop_in_sese (region
, GBB_BB (PBB_BLACK_BOX (pbb
)));
1785 if (loop_in_sese_p (loop
, region
))
1786 res
= loop_to_lst (loop
, SCOP_BBS (scop
), &i
);
1788 res
= new_lst_stmt (pbb
);
1790 VEC_safe_push (lst_p
, heap
, seq
, res
);
1793 res
= new_lst_loop (seq
);
1794 SCOP_ORIGINAL_SCHEDULE (scop
) = res
;
1795 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (res
);
1798 /* Print to FILE on a new line COLUMN white spaces. */
1801 lst_indent_to (FILE *file
, int column
)
1806 fprintf (file
, "\n#");
1808 for (i
= 0; i
< column
; i
++)
1809 fprintf (file
, " ");
1812 /* Print LST to FILE with INDENT spaces of indentation. */
1815 print_lst (FILE *file
, lst_p lst
, int indent
)
1820 lst_indent_to (file
, indent
);
1822 if (LST_LOOP_P (lst
))
1827 if (LST_LOOP_FATHER (lst
))
1828 fprintf (file
, "%d (loop", lst_dewey_number (lst
));
1830 fprintf (file
, "#(root");
1832 FOR_EACH_VEC_ELT (lst_p
, LST_SEQ (lst
), i
, l
)
1833 print_lst (file
, l
, indent
+ 2);
1835 fprintf (file
, ")");
1838 fprintf (file
, "%d stmt_%d", lst_dewey_number (lst
), pbb_index (LST_PBB (lst
)));
1841 /* Print LST to STDERR. */
1844 debug_lst (lst_p lst
)
1846 print_lst (stderr
, lst
, 0);
1849 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1852 dot_lst_1 (FILE *file
, lst_p lst
)
1857 if (LST_LOOP_P (lst
))
1862 if (!LST_LOOP_FATHER (lst
))
1863 fprintf (file
, "L -> L_%d_%d\n",
1865 lst_dewey_number (lst
));
1867 fprintf (file
, "L_%d_%d -> L_%d_%d\n",
1868 lst_depth (LST_LOOP_FATHER (lst
)),
1869 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1871 lst_dewey_number (lst
));
1873 FOR_EACH_VEC_ELT (lst_p
, LST_SEQ (lst
), i
, l
)
1874 dot_lst_1 (file
, l
);
1878 fprintf (file
, "L_%d_%d -> S_%d\n",
1879 lst_depth (LST_LOOP_FATHER (lst
)),
1880 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1881 pbb_index (LST_PBB (lst
)));
1885 /* Display the LST using dotty. */
1890 /* When debugging, enable the following code. This cannot be used
1891 in production compilers because it calls "system". */
1893 FILE *stream
= fopen ("/tmp/lst.dot", "w");
1894 gcc_assert (stream
);
1896 fputs ("digraph all {\n", stream
);
1897 dot_lst_1 (stream
, lst
);
1898 fputs ("}\n\n", stream
);
1901 system ("dotty /tmp/lst.dot &");
1903 fputs ("digraph all {\n", stderr
);
1904 dot_lst_1 (stderr
, lst
);
1905 fputs ("}\n\n", stderr
);
1910 /* Computes a checksum for the code generated by CLooG for SCOP. */
1913 cloog_checksum (scop_p scop ATTRIBUTE_UNUSED
)
1915 /* When debugging, enable the following code. This cannot be used
1916 in production compilers because it calls "system". */
1918 FILE *stream
= fopen ("/tmp/scop.cloog", "w");
1919 gcc_assert (stream
);
1920 print_cloog (stream
, scop
, 0);
1923 fputs ("\n", stdout
);
1924 system ("cloog -compilable 1 /tmp/scop.cloog > /tmp/scop.c ; gcc -O0 -g /tmp/scop.c -lm -o /tmp/scop; /tmp/scop | md5sum ");