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"
55 #include "graphite-cloog-util.h"
57 #define OPENSCOP_MAX_STRING 256
59 /* Return the maximal loop depth in SCOP. */
62 scop_max_loop_depth (scop_p scop
)
68 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
70 int nb_loops
= pbb_dim_iter_domain (pbb
);
71 if (max_nb_loops
< nb_loops
)
72 max_nb_loops
= nb_loops
;
78 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
82 extend_scattering (poly_bb_p pbb
, int max_scattering
)
84 ppl_dimension_type nb_old_dims
, nb_new_dims
;
86 ppl_Coefficient_t coef
;
89 nb_added_dims
= max_scattering
- pbb_nb_scattering_transform (pbb
);
92 ppl_new_Coefficient (&coef
);
93 ppl_assign_Coefficient_from_mpz_t (coef
, one
);
95 gcc_assert (nb_added_dims
>= 0);
97 nb_old_dims
= pbb_nb_scattering_transform (pbb
) + pbb_dim_iter_domain (pbb
)
98 + scop_nb_params (PBB_SCOP (pbb
));
99 nb_new_dims
= nb_old_dims
+ nb_added_dims
;
101 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
),
102 pbb_nb_scattering_transform (pbb
), nb_added_dims
);
103 PBB_NB_SCATTERING_TRANSFORM (pbb
) += nb_added_dims
;
105 /* Add identity matrix for the added dimensions. */
106 for (i
= max_scattering
- nb_added_dims
; i
< max_scattering
; i
++)
108 ppl_Constraint_t cstr
;
109 ppl_Linear_Expression_t expr
;
111 ppl_new_Linear_Expression_with_dimension (&expr
, nb_new_dims
);
112 ppl_Linear_Expression_add_to_coefficient (expr
, i
, coef
);
113 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
114 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
115 ppl_delete_Constraint (cstr
);
116 ppl_delete_Linear_Expression (expr
);
119 ppl_delete_Coefficient (coef
);
123 /* All scattering matrices in SCOP will have the same number of scattering
127 unify_scattering_dimensions (scop_p scop
)
131 graphite_dim_t max_scattering
= 0;
133 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
134 max_scattering
= MAX (pbb_nb_scattering_transform (pbb
), max_scattering
);
136 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
137 extend_scattering (pbb
, max_scattering
);
139 return max_scattering
;
142 /* Print to FILE the pdr PH in OpenScop format. NB_SUBSCRIPTS is the number
143 of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and
144 NB_PARAMS is the number of parameters in PH. */
147 openscop_print_pdr_polyhedron (FILE *file
, ppl_const_Polyhedron_t ph
,
148 int nb_subscripts
, int alias_set_dimension
,
151 int input
, locals
, output
;
152 ppl_dimension_type alias_set_dim
= (ppl_dimension_type
) alias_set_dimension
;
153 ppl_dimension_type sub_dim_last
= alias_set_dim
+ nb_subscripts
;
154 ppl_dimension_type
*map
, i
, ph_space_dim
= sub_dim_last
+ 1;
155 ppl_Polyhedron_t pph
;
157 ppl_new_C_Polyhedron_from_C_Polyhedron (&pph
, ph
);
159 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, ph_space_dim
);
161 for (i
= 0; i
< alias_set_dim
- 1; i
++)
162 map
[i
] = nb_subscripts
+ 1 + i
;
164 for (i
= alias_set_dim
- 1; i
< sub_dim_last
; i
++)
165 map
[i
] = i
- alias_set_dim
+ 1;
167 ppl_Polyhedron_map_space_dimensions (pph
, map
, ph_space_dim
- 1);
170 input
= alias_set_dim
- nb_params
- 1;
172 /* According to OpenScop specification, the alias set column is a part of
173 the output columns. */
174 output
= nb_subscripts
+ 1;
176 openscop_print_polyhedron_matrix (file
, pph
, output
, input
, locals
, nb_params
);
179 /* Print to FILE the powerset PDR. NB_SUBSCRIPTS is the number of subscripts
180 in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and
181 NB_PARAMS is the number of parameters in PDR. */
184 openscop_print_pdr_powerset (FILE *file
,
185 ppl_Pointset_Powerset_C_Polyhedron_t ps
,
191 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it
, end
;
193 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it
);
194 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end
);
196 ppl_Pointset_Powerset_C_Polyhedron_size (ps
, &nb_disjuncts
);
197 fprintf (file
, "%d\n", (int) nb_disjuncts
);
199 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps
, it
),
200 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps
, end
);
201 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it
, end
);
202 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it
))
204 ppl_const_Polyhedron_t ph
;
206 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it
, &ph
);
207 openscop_print_pdr_polyhedron (file
, ph
, nb_subscripts
, alias_set_dim
,
211 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it
);
212 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end
);
215 /* Print to FILE the powerset PS in its OpenScop matrix form. */
218 openscop_print_powerset_matrix (FILE *file
,
219 ppl_Pointset_Powerset_C_Polyhedron_t ps
,
220 int output
, int input
, int locals
,
224 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it
, end
;
226 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it
);
227 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end
);
229 ppl_Pointset_Powerset_C_Polyhedron_size (ps
, &nb_disjuncts
);
230 fprintf (file
, "%d\n", (int) nb_disjuncts
);
232 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps
, it
),
233 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps
, end
);
234 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it
, end
);
235 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it
))
237 ppl_const_Polyhedron_t ph
;
239 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it
, &ph
);
240 openscop_print_polyhedron_matrix (file
, ph
, output
, input
, locals
,
244 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it
);
245 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end
);
248 /* Prints to FILE the scattering function of PBB in OpenScop format, at some
252 openscop_print_scattering_function_1 (FILE *file
, poly_bb_p pbb
, int verbosity
)
255 ppl_const_Polyhedron_t ph
;
259 fprintf (file
, "# scattering bb_%d (\n", pbb_index (pbb
));
260 fprintf (file
, "#eq");
262 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
263 fprintf (file
, " s%d", (int) i
);
265 for (i
= 0; i
< pbb_nb_local_vars (pbb
); i
++)
266 fprintf (file
, " lv%d", (int) i
);
268 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
269 fprintf (file
, " i%d", (int) i
);
271 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
272 fprintf (file
, " p%d", (int) i
);
274 fprintf (file
, " cst\n");
277 /* Number of disjunct components. Remove this when
278 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
279 fprintf (file
, "1\n");
281 ph
= PBB_TRANSFORMED_SCATTERING (pbb
)
282 ? PBB_TRANSFORMED_SCATTERING (pbb
)
283 : PBB_ORIGINAL_SCATTERING (pbb
);
285 openscop_print_polyhedron_matrix (file
, ph
,
286 pbb_nb_scattering_transform (pbb
),
287 pbb_dim_iter_domain (pbb
),
288 pbb_nb_local_vars (pbb
),
289 pbb_nb_params (pbb
));
292 fprintf (file
, "#)\n");
295 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
299 print_scattering_function_1 (FILE *file
, poly_bb_p pbb
, int verbosity
)
305 fprintf (file
, "# scattering bb_%d (\n", pbb_index (pbb
));
306 fprintf (file
, "#eq");
308 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
309 fprintf (file
, " s%d", (int) i
);
311 for (i
= 0; i
< pbb_nb_local_vars (pbb
); i
++)
312 fprintf (file
, " lv%d", (int) i
);
314 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
315 fprintf (file
, " i%d", (int) i
);
317 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
318 fprintf (file
, " p%d", (int) i
);
320 fprintf (file
, " cst\n");
323 /* Number of disjunct components. Remove this when
324 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
325 fprintf (file
, "1\n");
326 ppl_print_polyhedron_matrix (file
, PBB_TRANSFORMED_SCATTERING (pbb
)
327 ? PBB_TRANSFORMED_SCATTERING (pbb
)
328 : PBB_ORIGINAL_SCATTERING (pbb
));
331 fprintf (file
, "#)\n");
334 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
338 print_scattering_function (FILE *file
, poly_bb_p pbb
, int verbosity
)
340 if (!PBB_TRANSFORMED (pbb
))
343 if (PBB_TRANSFORMED_SCATTERING (pbb
)
344 || PBB_ORIGINAL_SCATTERING (pbb
))
347 fprintf (file
, "# Scattering function is provided\n");
349 fprintf (file
, "1\n");
354 fprintf (file
, "# Scattering function is not provided\n");
356 fprintf (file
, "0\n");
360 openscop_print_scattering_function_1 (file
, pbb
, verbosity
);
363 fprintf (file
, "# Scattering names are not provided\n");
365 fprintf (file
, "0\n");
369 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
373 print_iteration_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
375 print_pbb_domain (file
, pbb
, verbosity
);
378 /* Prints to FILE the scattering functions of every PBB of SCOP. */
381 print_scattering_functions (FILE *file
, scop_p scop
, int verbosity
)
386 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
387 print_scattering_function (file
, pbb
, verbosity
);
390 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
394 print_iteration_domains (FILE *file
, scop_p scop
, int verbosity
)
399 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
400 print_iteration_domain (file
, pbb
, verbosity
);
403 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
407 debug_scattering_function (poly_bb_p pbb
, int verbosity
)
409 print_scattering_function (stderr
, pbb
, verbosity
);
412 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
416 debug_iteration_domain (poly_bb_p pbb
, int verbosity
)
418 print_iteration_domain (stderr
, pbb
, verbosity
);
421 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
422 some VERBOSITY level. */
425 debug_scattering_functions (scop_p scop
, int verbosity
)
427 print_scattering_functions (stderr
, scop
, verbosity
);
430 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
431 some VERBOSITY level. */
434 debug_iteration_domains (scop_p scop
, int verbosity
)
436 print_iteration_domains (stderr
, scop
, verbosity
);
439 /* Read N integer from FILE. */
442 openscop_read_N_int (FILE *file
, int N
)
444 char s
[OPENSCOP_MAX_STRING
];
446 int i
, *res
= (int *) xmalloc (OPENSCOP_MAX_STRING
* sizeof (int));
448 /* Skip blank and commented lines. */
449 while (fgets (s
, sizeof s
, file
) == (char *) 0
456 for (i
= 0; i
< N
; i
++)
458 sscanf (str
, "%d", &res
[i
]);
460 /* Jump the integer that was read. */
461 while ((*str
) && !ISSPACE (*str
) && (*str
!= '#'))
465 while ((*str
) && ISSPACE (*str
) && (*str
!= '#'))
472 /* Read one integer from FILE. */
475 openscop_read_one_int (FILE *file
)
477 int *x
= openscop_read_N_int (file
, 1);
484 /* Read N string from FILE. */
487 openscop_read_N_string (FILE *file
, int N
)
490 char str
[OPENSCOP_MAX_STRING
];
491 char *tmp
= (char *) xmalloc (sizeof (char) * OPENSCOP_MAX_STRING
);
494 /* Skip blank and commented lines. */
495 while (fgets (str
, sizeof str
, file
) == (char *) 0
503 for (i
= 0; i
< N
; i
++)
505 /* Read the first word. */
506 for (; (*s
) && (!ISSPACE (*s
)) && (*s
!= '#'); ++count
)
513 while ((*s
) && ISSPACE (*s
) && (*s
!= '#'))
522 /* Read one string from FILE. */
525 openscop_read_one_string (FILE *file
)
527 return openscop_read_N_string (file
, 1);
530 /* Read from FILE the powerset PS in its OpenScop matrix form. OUTPUT is the
531 number of output dimensions, INPUT is the number of input dimensions,
532 LOCALS is the number of existentially quantified variables and PARAMS is
533 the number of parameters. */
536 openscop_read_powerset_matrix (FILE *file
,
537 ppl_Pointset_Powerset_C_Polyhedron_t
*ps
,
538 int *output
, int *input
, int *locals
,
543 nb_disjuncts
= openscop_read_one_int (file
);
545 for (i
= 0; i
< nb_disjuncts
; i
++)
549 openscop_read_polyhedron_matrix (file
, &ph
, output
, input
, locals
,
554 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (ps
, ph
);
556 ppl_Pointset_Powerset_C_Polyhedron_add_disjunct (*ps
, ph
);
560 /* Read a scattering function from FILE and save it to PBB. Return whether
561 the scattering function was provided or not. */
564 graphite_read_scatt (FILE *file
, poly_bb_p pbb
)
566 bool scattering_provided
= false;
567 int output
, input
, locals
, params
;
568 ppl_Polyhedron_t newp
;
570 if (openscop_read_one_int (file
) > 0)
572 /* Read number of disjunct components. */
573 openscop_read_one_int (file
);
575 /* Read scattering function. */
576 openscop_read_polyhedron_matrix (file
, &newp
, &output
, &input
,
578 store_scattering (PBB_SCOP (pbb
));
579 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
580 PBB_TRANSFORMED_SCATTERING (pbb
) = newp
;
581 PBB_NB_LOCAL_VARIABLES (pbb
) = locals
;
583 /* New scattering dimension. */
584 PBB_NB_SCATTERING_TRANSFORM (pbb
) = output
;
586 scattering_provided
= true;
589 return scattering_provided
;
592 /* Read a scop file. Return true if the scop is transformed. */
595 graphite_read_scop_file (FILE *file
, scop_p scop
)
597 char *tmp
, *language
;
598 size_t i
, j
, nb_statements
, nbr
, nbw
;
599 int input
, output
, locals
, params
;
600 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
602 bool transform_done
= false;
604 /* Ensure that the file is in OpenScop format. */
605 tmp
= openscop_read_N_string (file
, 2);
607 if (strcmp (tmp
, "SCoP 1"))
609 error ("The file is not in OpenScop format.\n");
615 /* Read the language. */
616 language
= openscop_read_one_string (file
);
618 if (strcmp (language
, "Gimple"))
620 error ("The language is not recognized\n");
626 /* Read the context but do not use it. */
627 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
, ¶ms
);
629 if ((size_t) params
!= scop
->nb_params
)
631 error ("Parameters number in the scop file is different from the"
632 " internal scop parameter number.");
636 /* Read parameter names if provided. */
637 if (openscop_read_one_int (file
))
638 openscop_read_N_string (file
, scop
->nb_params
);
640 nb_statements
= openscop_read_one_int (file
);
642 if (nb_statements
!= VEC_length (poly_bb_p
, SCOP_BBS (scop
)))
644 error ("Number of statements in the OpenScop file does not match"
645 " the graphite internal statements number.");
649 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
651 /* Read iteration domain. */
652 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
,
655 /* Read scattering. */
656 transform_done
= graphite_read_scatt (file
, pbb
);
658 /* Scattering names. */
659 openscop_read_one_int (file
);
661 /* Read access functions. */
662 if (openscop_read_one_int (file
) > 0)
664 nbr
= openscop_read_one_int (file
);
666 /* Read access functions. */
667 for (j
= 0; j
< nbr
; j
++)
668 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
,
671 nbw
= openscop_read_one_int (file
);
673 /* Write access functions. */
674 for (j
= 0; j
< nbw
; j
++)
675 openscop_read_powerset_matrix (file
, &ps
, &input
, &output
, &locals
,
679 /* Statement body. */
680 openscop_read_one_int (file
);
683 return transform_done
;
686 /* Initialize and return a file that will be used to write a scop. SCOP_NUMBER
687 is a sequential number (identifier) used to differentiate scop files.
688 Examples of the generated file names: dump_base_name.0.graphite,
689 dump_base_name.1.graphite, dump_base_name.2.graphite, etc. */
692 init_graphite_out_file (int scop_number
)
694 FILE *graphite_out_file
;
695 int len
= strlen (dump_base_name
);
696 char *dumpname
= XNEWVEC (char, len
+ 25);
697 char *s_scop_number
= XNEWVEC (char, 15);
699 memcpy (dumpname
, dump_base_name
, len
+ 1);
700 strip_off_ending (dumpname
, len
);
701 sprintf (s_scop_number
, ".%d", scop_number
);
702 strcat (dumpname
, s_scop_number
);
703 strcat (dumpname
, ".graphite");
704 graphite_out_file
= fopen (dumpname
, "w+b");
706 if (graphite_out_file
== 0)
707 fatal_error ("can%'t open %s for writing: %m", dumpname
);
711 return graphite_out_file
;
714 /* Open and return a file used for scop reading. SCOP_NUMBER is a sequential
715 number (identifier) used to differentiate scop files. Examples of the
716 generated file names: dump_base_name.0.graphite, dump_base_name.1.graphite,
717 dump_base_name.2.graphite, etc. */
720 init_graphite_in_file (int scop_number
)
722 FILE *graphite_in_file
;
723 int len
= strlen (dump_base_name
);
724 char *dumpname
= XNEWVEC (char, len
+ 25);
725 char *s_scop_number
= XNEWVEC (char, 15);
727 memcpy (dumpname
, dump_base_name
, len
+ 1);
728 strip_off_ending (dumpname
, len
);
729 sprintf (s_scop_number
, ".%d", scop_number
);
730 strcat (dumpname
, s_scop_number
);
731 strcat (dumpname
, ".graphite");
732 graphite_in_file
= fopen (dumpname
, "r+b");
734 if (graphite_in_file
== 0)
735 fatal_error ("can%'t open %s for reading: %m", dumpname
);
739 return graphite_in_file
;
742 /* Apply graphite transformations to all the basic blocks of SCOP. */
745 apply_poly_transforms (scop_p scop
)
747 bool transform_done
= false;
749 static size_t file_scop_number
= 0;
751 /* This feature is only enabled in the Graphite branch. */
754 graphite_file
= init_graphite_in_file (file_scop_number
);
755 transform_done
|= graphite_read_scop_file (graphite_file
, scop
);
757 if (!graphite_legal_transform (scop
))
758 fatal_error ("the graphite file read for scop %d does not contain a legal transform",
759 (int) file_scop_number
);
764 /* Generate code even if we did not apply any real transformation.
765 This also allows to check the performance for the identity
766 transformation: GIMPLE -> GRAPHITE -> GIMPLE
767 Keep in mind that CLooG optimizes in control, so the loop structure
768 may change, even if we only use -fgraphite-identity. */
769 if (flag_graphite_identity
)
770 transform_done
= true;
772 if (flag_loop_parallelize_all
)
773 transform_done
= true;
776 transform_done
|= scop_do_block (scop
);
779 if (flag_loop_strip_mine
)
780 transform_done
|= scop_do_strip_mine (scop
);
782 if (flag_loop_interchange
)
783 transform_done
|= scop_do_interchange (scop
);
786 if (flag_loop_flatten
)
787 transform_done
|= flatten_all_loops (scop
);
789 /* This feature is only enabled in the Graphite branch. */
792 graphite_file
= init_graphite_out_file (file_scop_number
);
793 print_scop (graphite_file
, scop
, 1);
797 return transform_done
;
800 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
801 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */
804 can_collapse_pdrs (poly_dr_p pdr1
, poly_dr_p pdr2
)
807 ppl_Pointset_Powerset_C_Polyhedron_t af1
, af2
, diff
;
809 if (PDR_PBB (pdr1
) != PDR_PBB (pdr2
)
810 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
)
811 || PDR_TYPE (pdr1
) != PDR_TYPE (pdr2
))
814 af1
= PDR_ACCESSES (pdr1
);
815 af2
= PDR_ACCESSES (pdr2
);
816 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
818 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff
, af2
);
820 res
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff
);
821 ppl_delete_Pointset_Powerset_C_Polyhedron (diff
);
825 /* Removes duplicated data references in PBB. */
828 pbb_remove_duplicate_pdrs (poly_bb_p pbb
)
831 poly_dr_p pdr1
, pdr2
;
832 unsigned n
= VEC_length (poly_dr_p
, PBB_DRS (pbb
));
833 VEC (poly_dr_p
, heap
) *collapsed
= VEC_alloc (poly_dr_p
, heap
, n
);
835 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr1
)
836 FOR_EACH_VEC_ELT (poly_dr_p
, collapsed
, j
, pdr2
)
837 if (!can_collapse_pdrs (pdr1
, pdr2
))
838 VEC_quick_push (poly_dr_p
, collapsed
, pdr1
);
840 VEC_free (poly_dr_p
, heap
, collapsed
);
841 PBB_PDR_DUPLICATES_REMOVED (pbb
) = true;
844 /* Create a new polyhedral data reference and add it to PBB. It is
845 defined by its ACCESSES, its TYPE, and the number of subscripts
849 new_poly_dr (poly_bb_p pbb
, int dr_base_object_set
,
850 ppl_Pointset_Powerset_C_Polyhedron_t accesses
,
851 enum poly_dr_type type
, void *cdr
, graphite_dim_t nb_subscripts
)
854 poly_dr_p pdr
= XNEW (struct poly_dr
);
857 PDR_BASE_OBJECT_SET (pdr
) = dr_base_object_set
;
858 PDR_NB_REFS (pdr
) = 1;
860 PDR_ACCESSES (pdr
) = accesses
;
861 PDR_TYPE (pdr
) = type
;
863 PDR_NB_SUBSCRIPTS (pdr
) = nb_subscripts
;
864 VEC_safe_push (poly_dr_p
, heap
, PBB_DRS (pbb
), pdr
);
867 /* Free polyhedral data reference PDR. */
870 free_poly_dr (poly_dr_p pdr
)
872 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr
));
876 /* Create a new polyhedral black box. */
879 new_poly_bb (scop_p scop
, void *black_box
, bool reduction
)
881 poly_bb_p pbb
= XNEW (struct poly_bb
);
883 PBB_DOMAIN (pbb
) = NULL
;
884 PBB_SCOP (pbb
) = scop
;
885 pbb_set_black_box (pbb
, black_box
);
886 PBB_TRANSFORMED (pbb
) = NULL
;
887 PBB_SAVED (pbb
) = NULL
;
888 PBB_ORIGINAL (pbb
) = NULL
;
889 PBB_DRS (pbb
) = VEC_alloc (poly_dr_p
, heap
, 3);
890 PBB_IS_REDUCTION (pbb
) = reduction
;
891 PBB_PDR_DUPLICATES_REMOVED (pbb
) = false;
892 VEC_safe_push (poly_bb_p
, heap
, SCOP_BBS (scop
), pbb
);
895 /* Free polyhedral black box. */
898 free_poly_bb (poly_bb_p pbb
)
903 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb
));
905 if (PBB_TRANSFORMED (pbb
))
906 poly_scattering_free (PBB_TRANSFORMED (pbb
));
909 poly_scattering_free (PBB_SAVED (pbb
));
911 if (PBB_ORIGINAL (pbb
))
912 poly_scattering_free (PBB_ORIGINAL (pbb
));
915 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
)
918 VEC_free (poly_dr_p
, heap
, PBB_DRS (pbb
));
923 print_pdr_access_layout (FILE *file
, poly_bb_p pbb
, poly_dr_p pdr
)
927 fprintf (file
, "# eq");
929 fprintf (file
, " alias");
931 for (i
= 0; i
< PDR_NB_SUBSCRIPTS (pdr
); i
++)
932 fprintf (file
, " sub%d", (int) i
);
934 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
935 fprintf (file
, " i%d", (int) i
);
937 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
938 fprintf (file
, " p%d", (int) i
);
940 fprintf (file
, " cst\n");
943 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
947 print_pdr (FILE *file
, poly_dr_p pdr
, int verbosity
)
953 fprintf (file
, "# pdr_%d (", PDR_ID (pdr
));
955 switch (PDR_TYPE (pdr
))
958 fprintf (file
, "read \n");
962 fprintf (file
, "write \n");
966 fprintf (file
, "may_write \n");
973 dump_data_reference (file
, (data_reference_p
) PDR_CDR (pdr
));
978 fprintf (file
, "# data accesses (\n");
979 print_pdr_access_layout (file
, PDR_PBB (pdr
), pdr
);
982 alias_set_dim
= pdr_alias_set_dim (pdr
) + 1;
984 openscop_print_pdr_powerset (file
,
986 PDR_NB_SUBSCRIPTS (pdr
),
988 pbb_nb_params (PDR_PBB (pdr
)));
991 fprintf (file
, "#)\n");
994 fprintf (file
, "#)\n");
997 /* Prints to STDERR the polyhedral data reference PDR, at some
1001 debug_pdr (poly_dr_p pdr
, int verbosity
)
1003 print_pdr (stderr
, pdr
, verbosity
);
1006 /* Creates a new SCOP containing REGION. */
1009 new_scop (void *region
)
1011 scop_p scop
= XNEW (struct scop
);
1013 SCOP_CONTEXT (scop
) = NULL
;
1014 scop_set_region (scop
, region
);
1015 SCOP_BBS (scop
) = VEC_alloc (poly_bb_p
, heap
, 3);
1016 SCOP_ORIGINAL_PDDRS (scop
) = htab_create (10, hash_poly_ddr_p
,
1017 eq_poly_ddr_p
, free_poly_ddr
);
1018 SCOP_ORIGINAL_SCHEDULE (scop
) = NULL
;
1019 SCOP_TRANSFORMED_SCHEDULE (scop
) = NULL
;
1020 SCOP_SAVED_SCHEDULE (scop
) = NULL
;
1021 POLY_SCOP_P (scop
) = false;
1029 free_scop (scop_p scop
)
1034 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1037 VEC_free (poly_bb_p
, heap
, SCOP_BBS (scop
));
1039 if (SCOP_CONTEXT (scop
))
1040 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop
));
1042 htab_delete (SCOP_ORIGINAL_PDDRS (scop
));
1043 free_lst (SCOP_ORIGINAL_SCHEDULE (scop
));
1044 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1045 free_lst (SCOP_SAVED_SCHEDULE (scop
));
1049 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
1053 openscop_print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
1056 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1058 if (!PBB_DOMAIN (pbb
))
1063 fprintf (file
, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
1064 fprintf (file
, "#eq");
1066 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
1067 fprintf (file
, " i%d", (int) i
);
1069 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
1070 fprintf (file
, " p%d", (int) i
);
1072 fprintf (file
, " cst\n");
1075 if (PBB_DOMAIN (pbb
))
1076 openscop_print_powerset_matrix (file
, PBB_DOMAIN (pbb
),
1077 pbb_dim_iter_domain (pbb
),
1080 pbb_nb_params (pbb
));
1082 fprintf (file
, "0\n");
1085 fprintf (file
, "#)\n");
1088 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
1091 print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
1094 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1096 if (!PBB_DOMAIN (pbb
))
1101 fprintf (file
, "# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
1102 fprintf (file
, "# eq");
1104 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
1105 fprintf (file
, " i%d", (int) i
);
1107 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
1108 fprintf (file
, " p%d", (int) i
);
1110 fprintf (file
, " cst\n");
1113 if (PBB_DOMAIN (pbb
))
1114 ppl_print_powerset_matrix (file
, PBB_DOMAIN (pbb
));
1116 fprintf (file
, "0\n");
1119 fprintf (file
, "#)\n");
1122 /* Dump the cases of a graphite basic block GBB on FILE. */
1125 dump_gbb_cases (FILE *file
, gimple_bb_p gbb
)
1129 VEC (gimple
, heap
) *cases
;
1134 cases
= GBB_CONDITION_CASES (gbb
);
1135 if (VEC_empty (gimple
, cases
))
1138 fprintf (file
, "# cases bb_%d (\n", GBB_BB (gbb
)->index
);
1140 FOR_EACH_VEC_ELT (gimple
, cases
, i
, stmt
)
1142 fprintf (file
, "# ");
1143 print_gimple_stmt (file
, stmt
, 0, 0);
1146 fprintf (file
, "#)\n");
1149 /* Dump conditions of a graphite basic block GBB on FILE. */
1152 dump_gbb_conditions (FILE *file
, gimple_bb_p gbb
)
1156 VEC (gimple
, heap
) *conditions
;
1161 conditions
= GBB_CONDITIONS (gbb
);
1162 if (VEC_empty (gimple
, conditions
))
1165 fprintf (file
, "# conditions bb_%d (\n", GBB_BB (gbb
)->index
);
1167 FOR_EACH_VEC_ELT (gimple
, conditions
, i
, stmt
)
1169 fprintf (file
, "# ");
1170 print_gimple_stmt (file
, stmt
, 0, 0);
1173 fprintf (file
, "#)\n");
1176 /* Print to FILE all the data references of PBB, at some VERBOSITY
1180 print_pdrs (FILE *file
, poly_bb_p pbb
, int verbosity
)
1187 if (VEC_length (poly_dr_p
, PBB_DRS (pbb
)) == 0)
1190 fprintf (file
, "# Access informations are not provided\n");\
1191 fprintf (file
, "0\n");
1196 fprintf (file
, "# Data references (\n");
1199 fprintf (file
, "# Access informations are provided\n");
1200 fprintf (file
, "1\n");
1202 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
)
1203 if (PDR_TYPE (pdr
) == PDR_READ
)
1209 fprintf (file
, "# Read data references (\n");
1212 fprintf (file
, "# Read access informations\n");
1213 fprintf (file
, "%d\n", nb_reads
);
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
, "# Write data references (\n");
1226 fprintf (file
, "# Write access informations\n");
1227 fprintf (file
, "%d\n", nb_writes
);
1229 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
)
1230 if (PDR_TYPE (pdr
) != PDR_READ
)
1231 print_pdr (file
, pdr
, verbosity
);
1234 fprintf (file
, "#)\n");
1237 fprintf (file
, "#)\n");
1240 /* Print to STDERR all the data references of PBB. */
1243 debug_pdrs (poly_bb_p pbb
, int verbosity
)
1245 print_pdrs (stderr
, pbb
, verbosity
);
1248 /* Print to FILE the body of PBB, at some VERBOSITY level.
1249 If statement_body_provided is false statement body is not printed. */
1252 print_pbb_body (FILE *file
, poly_bb_p pbb
, int verbosity
,
1253 bool statement_body_provided
)
1256 fprintf (file
, "# Body (\n");
1258 if (!statement_body_provided
)
1261 fprintf (file
, "# Statement body is not provided\n");
1263 fprintf (file
, "0\n");
1266 fprintf (file
, "#)\n");
1271 fprintf (file
, "# Statement body is provided\n");
1272 fprintf (file
, "1\n");
1275 fprintf (file
, "# Original iterator names\n# Iterator names are not provided yet.\n");
1278 fprintf (file
, "# Statement body\n");
1280 fprintf (file
, "{\n");
1281 dump_bb (pbb_bb (pbb
), file
, 0);
1282 fprintf (file
, "}\n");
1285 fprintf (file
, "#)\n");
1288 /* Print to FILE the domain and scattering function of PBB, at some
1292 print_pbb (FILE *file
, poly_bb_p pbb
, int verbosity
)
1296 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1297 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
1298 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
1301 openscop_print_pbb_domain (file
, pbb
, verbosity
);
1302 print_scattering_function (file
, pbb
, verbosity
);
1303 print_pdrs (file
, pbb
, verbosity
);
1304 print_pbb_body (file
, pbb
, verbosity
, false);
1307 fprintf (file
, "#)\n");
1310 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
1313 print_scop_params (FILE *file
, scop_p scop
, int verbosity
)
1319 fprintf (file
, "# parameters (\n");
1321 if (VEC_length (tree
, SESE_PARAMS (SCOP_REGION (scop
))))
1324 fprintf (file
, "# Parameter names are provided\n");
1326 fprintf (file
, "1\n");
1329 fprintf (file
, "# Parameter names\n");
1334 fprintf (file
, "# Parameter names are not provided\n");
1335 fprintf (file
, "0\n");
1338 FOR_EACH_VEC_ELT (tree
, SESE_PARAMS (SCOP_REGION (scop
)), i
, t
)
1340 print_generic_expr (file
, t
, 0);
1341 fprintf (file
, " ");
1344 fprintf (file
, "\n");
1347 fprintf (file
, "#)\n");
1350 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1354 openscop_print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
1360 fprintf (file
, "# Context (\n");
1361 fprintf (file
, "#eq");
1363 for (i
= 0; i
< scop_nb_params (scop
); i
++)
1364 fprintf (file
, " p%d", (int) i
);
1366 fprintf (file
, " cst\n");
1369 if (SCOP_CONTEXT (scop
))
1370 openscop_print_powerset_matrix (file
, SCOP_CONTEXT (scop
), 0, 0, 0,
1371 scop_nb_params (scop
));
1373 fprintf (file
, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop
) + 2,
1374 (int) scop_nb_params (scop
));
1377 fprintf (file
, "# )\n");
1380 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
1383 print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
1389 fprintf (file
, "# Context (\n");
1390 fprintf (file
, "#eq");
1392 for (i
= 0; i
< scop_nb_params (scop
); i
++)
1393 fprintf (file
, " p%d", (int) i
);
1395 fprintf (file
, " cst\n");
1398 if (SCOP_CONTEXT (scop
))
1399 ppl_print_powerset_matrix (file
, SCOP_CONTEXT (scop
));
1401 fprintf (file
, "0 %d\n", (int) scop_nb_params (scop
) + 2);
1404 fprintf (file
, "# )\n");
1407 /* Print to FILE the SCOP, at some VERBOSITY level. */
1410 print_scop (FILE *file
, scop_p scop
, int verbosity
)
1415 fprintf (file
, "SCoP 1\n#(\n");
1416 fprintf (file
, "# Language\nGimple\n");
1417 openscop_print_scop_context (file
, scop
, verbosity
);
1418 print_scop_params (file
, scop
, verbosity
);
1421 fprintf (file
, "# Number of statements\n");
1423 fprintf (file
, "%d\n",VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1425 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1426 print_pbb (file
, pbb
, verbosity
);
1430 fprintf (file
, "# original_lst (\n");
1431 print_lst (file
, SCOP_ORIGINAL_SCHEDULE (scop
), 0);
1432 fprintf (file
, "\n#)\n");
1434 fprintf (file
, "# transformed_lst (\n");
1435 print_lst (file
, SCOP_TRANSFORMED_SCHEDULE (scop
), 0);
1436 fprintf (file
, "\n#)\n");
1439 fprintf (file
, "#)\n");
1442 /* Print to FILE the input file that CLooG would expect as input, at
1443 some VERBOSITY level. */
1446 print_cloog (FILE *file
, scop_p scop
, int verbosity
)
1451 fprintf (file
, "# SCoP (generated by GCC/Graphite\n");
1453 fprintf (file
, "# CLooG output language\n");
1454 fprintf (file
, "c\n");
1456 print_scop_context (file
, scop
, verbosity
);
1457 print_scop_params (file
, scop
, verbosity
);
1460 fprintf (file
, "# Number of statements\n");
1462 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1464 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1467 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1469 print_pbb_domain (file
, pbb
, verbosity
);
1470 fprintf (file
, "0 0 0");
1473 fprintf (file
, "# For future CLooG options.\n");
1475 fprintf (file
, "\n");
1478 fprintf (file
, "#)\n");
1481 fprintf (file
, "0");
1483 fprintf (file
, "# Don't set the iterator names.\n");
1485 fprintf (file
, "\n");
1488 fprintf (file
, "# Number of scattering functions\n");
1490 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1491 unify_scattering_dimensions (scop
);
1493 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1495 if (!PBB_TRANSFORMED (pbb
)
1496 || !(PBB_TRANSFORMED_SCATTERING (pbb
)
1497 || PBB_ORIGINAL_SCATTERING (pbb
)))
1501 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1503 print_scattering_function_1 (file
, pbb
, verbosity
);
1506 fprintf (file
, "#)\n");
1509 fprintf (file
, "0");
1511 fprintf (file
, "# Don't set the scattering dimension names.\n");
1513 fprintf (file
, "\n");
1515 fprintf (file
, "#)\n");
1518 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
1521 debug_pbb_domain (poly_bb_p pbb
, int verbosity
)
1523 print_pbb_domain (stderr
, pbb
, verbosity
);
1526 /* Print to FILE the domain and scattering function of PBB, at some
1530 debug_pbb (poly_bb_p pbb
, int verbosity
)
1532 print_pbb (stderr
, pbb
, verbosity
);
1535 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
1538 debug_scop_context (scop_p scop
, int verbosity
)
1540 print_scop_context (stderr
, scop
, verbosity
);
1543 /* Print to STDERR the SCOP, at some VERBOSITY level. */
1546 debug_scop (scop_p scop
, int verbosity
)
1548 print_scop (stderr
, scop
, verbosity
);
1551 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1555 debug_cloog (scop_p scop
, int verbosity
)
1557 print_cloog (stderr
, scop
, verbosity
);
1560 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1564 debug_scop_params (scop_p scop
, int verbosity
)
1566 print_scop_params (stderr
, scop
, verbosity
);
1570 /* The dimension in the transformed scattering polyhedron of PBB
1571 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
1574 psct_scattering_dim_for_loop_depth (poly_bb_p pbb
, graphite_dim_t loop_depth
)
1576 ppl_const_Constraint_System_t pcs
;
1577 ppl_Constraint_System_const_iterator_t cit
, cend
;
1578 ppl_const_Constraint_t cstr
;
1579 ppl_Polyhedron_t ph
= PBB_TRANSFORMED_SCATTERING (pbb
);
1580 ppl_dimension_type iter
= psct_iterator_dim (pbb
, loop_depth
);
1581 ppl_Linear_Expression_t expr
;
1582 ppl_Coefficient_t coef
;
1587 ppl_new_Coefficient (&coef
);
1588 ppl_Polyhedron_get_constraints (ph
, &pcs
);
1589 ppl_new_Constraint_System_const_iterator (&cit
);
1590 ppl_new_Constraint_System_const_iterator (&cend
);
1592 for (ppl_Constraint_System_begin (pcs
, cit
),
1593 ppl_Constraint_System_end (pcs
, cend
);
1594 !ppl_Constraint_System_const_iterator_equal_test (cit
, cend
);
1595 ppl_Constraint_System_const_iterator_increment (cit
))
1597 ppl_Constraint_System_const_iterator_dereference (cit
, &cstr
);
1598 ppl_new_Linear_Expression_from_Constraint (&expr
, cstr
);
1599 ppl_Linear_Expression_coefficient (expr
, iter
, coef
);
1600 ppl_Coefficient_to_mpz_t (coef
, val
);
1602 if (mpz_sgn (val
) == 0)
1604 ppl_delete_Linear_Expression (expr
);
1608 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
1610 ppl_dimension_type scatter
= psct_scattering_dim (pbb
, i
);
1612 ppl_Linear_Expression_coefficient (expr
, scatter
, coef
);
1613 ppl_Coefficient_to_mpz_t (coef
, val
);
1615 if (mpz_sgn (val
) != 0)
1618 ppl_delete_Linear_Expression (expr
);
1619 ppl_delete_Coefficient (coef
);
1620 ppl_delete_Constraint_System_const_iterator (cit
);
1621 ppl_delete_Constraint_System_const_iterator (cend
);
1631 /* Returns the number of iterations RES of the loop around PBB at
1632 time(scattering) dimension TIME_DEPTH. */
1635 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
1636 graphite_dim_t time_depth
,
1639 ppl_Pointset_Powerset_C_Polyhedron_t domain
, sctr_lb
, sctr_ub
;
1640 ppl_dimension_type domain_dim
, sctr_dim
;
1641 ppl_Linear_Expression_t le
;
1642 mpz_t lb
, ub
, diff
, one
;
1645 ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb
), &sctr_dim
);
1647 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1648 (&domain
, PBB_DOMAIN (pbb
));
1650 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain
, &domain_dim
);
1655 mpz_set_si (one
, 1);
1657 /* Compute the upper bound on the original iteration domain and add
1658 that upper bound to the scattering. */
1659 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1660 (&sctr_ub
, PBB_TRANSFORMED_SCATTERING (pbb
));
1661 for (i
= 0; i
< (int) domain_dim
; i
++)
1663 ppl_Linear_Expression_t eq
;
1664 ppl_Constraint_t pc
;
1665 ppl_Constraint_System_t cs
;
1666 ppl_Polyhedron_t ph
;
1667 ppl_Pointset_Powerset_C_Polyhedron_t pph
;
1669 ppl_new_Linear_Expression_with_dimension (&le
, domain_dim
);
1670 ppl_set_coef (le
, i
, 1);
1671 ppl_min_for_le_pointset (domain
, le
, lb
);
1672 ppl_max_for_le_pointset (domain
, le
, ub
);
1673 mpz_sub (diff
, ub
, lb
);
1674 mpz_add (diff
, diff
, one
);
1676 ppl_new_Linear_Expression_with_dimension (&eq
, sctr_dim
);
1677 ppl_set_coef (eq
, psct_iterator_dim (pbb
, i
), -1);
1678 ppl_set_inhomogeneous_gmp (eq
, diff
);
1680 ppl_new_Constraint (&pc
, eq
, PPL_CONSTRAINT_TYPE_EQUAL
);
1681 ppl_new_Constraint_System_from_Constraint (&cs
, pc
);
1682 ppl_new_C_Polyhedron_from_Constraint_System (&ph
, cs
);
1683 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph
, ph
);
1684 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub
, pph
);
1686 ppl_delete_Linear_Expression (le
);
1687 ppl_delete_Linear_Expression (eq
);
1688 ppl_delete_Polyhedron (ph
);
1689 ppl_delete_Pointset_Powerset_C_Polyhedron (pph
);
1690 ppl_delete_Constraint (pc
);
1691 ppl_delete_Constraint_System (cs
);
1694 /* Compute the lower bound on the original iteration domain and add
1695 it to the scattering. */
1696 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1697 (&sctr_lb
, PBB_TRANSFORMED_SCATTERING (pbb
));
1698 for (i
= 0; i
< (int) domain_dim
; i
++)
1700 ppl_Linear_Expression_t eq
;
1701 ppl_Constraint_t pc
;
1702 ppl_Constraint_System_t cs
;
1703 ppl_Polyhedron_t ph
;
1704 ppl_Pointset_Powerset_C_Polyhedron_t pph
;
1706 ppl_new_Linear_Expression_with_dimension (&le
, domain_dim
);
1707 ppl_set_coef (le
, i
, 1);
1708 ppl_min_for_le_pointset (domain
, le
, lb
);
1710 ppl_new_Linear_Expression_with_dimension (&eq
, sctr_dim
);
1711 ppl_set_coef (eq
, psct_iterator_dim (pbb
, i
), -1);
1712 ppl_set_inhomogeneous_gmp (eq
, lb
);
1714 ppl_new_Constraint (&pc
, eq
, PPL_CONSTRAINT_TYPE_EQUAL
);
1715 ppl_new_Constraint_System_from_Constraint (&cs
, pc
);
1716 ppl_new_C_Polyhedron_from_Constraint_System (&ph
, cs
);
1717 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph
, ph
);
1718 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb
, pph
);
1720 ppl_delete_Linear_Expression (le
);
1721 ppl_delete_Linear_Expression (eq
);
1722 ppl_delete_Polyhedron (ph
);
1723 ppl_delete_Pointset_Powerset_C_Polyhedron (pph
);
1724 ppl_delete_Constraint (pc
);
1725 ppl_delete_Constraint_System (cs
);
1728 /* Extract the number of iterations. */
1729 ppl_new_Linear_Expression_with_dimension (&le
, sctr_dim
);
1730 ppl_set_coef (le
, time_depth
, 1);
1731 ppl_min_for_le_pointset (sctr_lb
, le
, lb
);
1732 ppl_max_for_le_pointset (sctr_ub
, le
, ub
);
1733 mpz_sub (res
, ub
, lb
);
1739 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub
);
1740 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb
);
1743 /* Translates LOOP to LST. */
1746 loop_to_lst (loop_p loop
, VEC (poly_bb_p
, heap
) *bbs
, int *i
)
1749 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1751 for (; VEC_iterate (poly_bb_p
, bbs
, *i
, pbb
); (*i
)++)
1754 basic_block bb
= GBB_BB (PBB_BLACK_BOX (pbb
));
1756 if (bb
->loop_father
== loop
)
1757 stmt
= new_lst_stmt (pbb
);
1758 else if (flow_bb_inside_loop_p (loop
, bb
))
1760 loop_p next
= loop
->inner
;
1762 while (next
&& !flow_bb_inside_loop_p (next
, bb
))
1765 stmt
= loop_to_lst (next
, bbs
, i
);
1770 return new_lst_loop (seq
);
1773 VEC_safe_push (lst_p
, heap
, seq
, stmt
);
1776 return new_lst_loop (seq
);
1779 /* Reads the original scattering of the SCOP and returns an LST
1783 scop_to_lst (scop_p scop
)
1786 int i
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
1787 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1788 sese region
= SCOP_REGION (scop
);
1790 for (i
= 0; i
< n
; i
++)
1792 poly_bb_p pbb
= VEC_index (poly_bb_p
, SCOP_BBS (scop
), i
);
1793 loop_p loop
= outermost_loop_in_sese (region
, GBB_BB (PBB_BLACK_BOX (pbb
)));
1795 if (loop_in_sese_p (loop
, region
))
1796 res
= loop_to_lst (loop
, SCOP_BBS (scop
), &i
);
1798 res
= new_lst_stmt (pbb
);
1800 VEC_safe_push (lst_p
, heap
, seq
, res
);
1803 res
= new_lst_loop (seq
);
1804 SCOP_ORIGINAL_SCHEDULE (scop
) = res
;
1805 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (res
);
1808 /* Print to FILE on a new line COLUMN white spaces. */
1811 lst_indent_to (FILE *file
, int column
)
1816 fprintf (file
, "\n#");
1818 for (i
= 0; i
< column
; i
++)
1819 fprintf (file
, " ");
1822 /* Print LST to FILE with INDENT spaces of indentation. */
1825 print_lst (FILE *file
, lst_p lst
, int indent
)
1830 lst_indent_to (file
, indent
);
1832 if (LST_LOOP_P (lst
))
1837 if (LST_LOOP_FATHER (lst
))
1838 fprintf (file
, "%d (loop", lst_dewey_number (lst
));
1840 fprintf (file
, "#(root");
1842 FOR_EACH_VEC_ELT (lst_p
, LST_SEQ (lst
), i
, l
)
1843 print_lst (file
, l
, indent
+ 2);
1845 fprintf (file
, ")");
1848 fprintf (file
, "%d stmt_%d", lst_dewey_number (lst
), pbb_index (LST_PBB (lst
)));
1851 /* Print LST to STDERR. */
1854 debug_lst (lst_p lst
)
1856 print_lst (stderr
, lst
, 0);
1859 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1862 dot_lst_1 (FILE *file
, lst_p lst
)
1867 if (LST_LOOP_P (lst
))
1872 if (!LST_LOOP_FATHER (lst
))
1873 fprintf (file
, "L -> L_%d_%d\n",
1875 lst_dewey_number (lst
));
1877 fprintf (file
, "L_%d_%d -> L_%d_%d\n",
1878 lst_depth (LST_LOOP_FATHER (lst
)),
1879 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1881 lst_dewey_number (lst
));
1883 FOR_EACH_VEC_ELT (lst_p
, LST_SEQ (lst
), i
, l
)
1884 dot_lst_1 (file
, l
);
1888 fprintf (file
, "L_%d_%d -> S_%d\n",
1889 lst_depth (LST_LOOP_FATHER (lst
)),
1890 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1891 pbb_index (LST_PBB (lst
)));
1895 /* Display the LST using dotty. */
1900 /* When debugging, enable the following code. This cannot be used
1901 in production compilers because it calls "system". */
1903 FILE *stream
= fopen ("/tmp/lst.dot", "w");
1904 gcc_assert (stream
);
1906 fputs ("digraph all {\n", stream
);
1907 dot_lst_1 (stream
, lst
);
1908 fputs ("}\n\n", stream
);
1911 system ("dotty /tmp/lst.dot &");
1913 fputs ("digraph all {\n", stderr
);
1914 dot_lst_1 (stderr
, lst
);
1915 fputs ("}\n\n", stderr
);
1920 /* Computes a checksum for the code generated by CLooG for SCOP. */
1923 cloog_checksum (scop_p scop ATTRIBUTE_UNUSED
)
1925 /* When debugging, enable the following code. This cannot be used
1926 in production compilers because it calls "system". */
1928 FILE *stream
= fopen ("/tmp/scop.cloog", "w");
1929 gcc_assert (stream
);
1930 print_cloog (stream
, scop
, 0);
1933 fputs ("\n", stdout
);
1934 system ("cloog -compilable 1 /tmp/scop.cloog > /tmp/scop.c ; gcc -O0 -g /tmp/scop.c -lm -o /tmp/scop; /tmp/scop | md5sum ");