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"
34 #include "tree-dump.h"
37 #include "tree-chrec.h"
38 #include "tree-data-ref.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-pass.h"
42 #include "value-prof.h"
43 #include "pointer-set.h"
50 #include "graphite-ppl.h"
52 #include "graphite-poly.h"
53 #include "graphite-dependences.h"
54 #include "graphite-cloog-util.h"
56 #define OPENSCOP_MAX_STRING 256
58 /* Return the maximal loop depth in SCOP. */
61 scop_max_loop_depth (scop_p scop)
67 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
69 int nb_loops = pbb_dim_iter_domain (pbb);
70 if (max_nb_loops < nb_loops)
71 max_nb_loops = nb_loops;
77 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
81 extend_scattering (poly_bb_p pbb, int max_scattering)
83 ppl_dimension_type nb_old_dims, nb_new_dims;
85 ppl_Coefficient_t coef;
88 nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb);
91 ppl_new_Coefficient (&coef);
92 ppl_assign_Coefficient_from_mpz_t (coef, one);
94 gcc_assert (nb_added_dims >= 0);
96 nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb)
97 + scop_nb_params (PBB_SCOP (pbb));
98 nb_new_dims = nb_old_dims + nb_added_dims;
100 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb),
101 pbb_nb_scattering_transform (pbb), nb_added_dims);
102 PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims;
104 /* Add identity matrix for the added dimensions. */
105 for (i = max_scattering - nb_added_dims; i < max_scattering; i++)
107 ppl_Constraint_t cstr;
108 ppl_Linear_Expression_t expr;
110 ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims);
111 ppl_Linear_Expression_add_to_coefficient (expr, i, coef);
112 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
113 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
114 ppl_delete_Constraint (cstr);
115 ppl_delete_Linear_Expression (expr);
118 ppl_delete_Coefficient (coef);
122 /* All scattering matrices in SCOP will have the same number of scattering
126 unify_scattering_dimensions (scop_p scop)
130 graphite_dim_t max_scattering = 0;
132 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
133 max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering);
135 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
136 extend_scattering (pbb, max_scattering);
138 return max_scattering;
141 /* Print to FILE the pdr PH in OpenScop format. NB_SUBSCRIPTS is the number
142 of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and
143 NB_PARAMS is the number of parameters in PH. */
146 openscop_print_pdr_polyhedron (FILE *file, ppl_const_Polyhedron_t ph,
147 int nb_subscripts, int alias_set_dimension,
150 int input, locals, output;
151 ppl_dimension_type alias_set_dim = (ppl_dimension_type) alias_set_dimension;
152 ppl_dimension_type sub_dim_last = alias_set_dim + nb_subscripts;
153 ppl_dimension_type *map, i, ph_space_dim = sub_dim_last + 1;
154 ppl_Polyhedron_t pph;
156 ppl_new_C_Polyhedron_from_C_Polyhedron (&pph, ph);
158 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, ph_space_dim);
160 for (i = 0; i < alias_set_dim - 1; i++)
161 map[i] = nb_subscripts + 1 + i;
163 for (i = alias_set_dim - 1; i < sub_dim_last; i++)
164 map[i] = i - alias_set_dim + 1;
166 ppl_Polyhedron_map_space_dimensions (pph, map, ph_space_dim - 1);
169 input = alias_set_dim - nb_params - 1;
171 /* According to OpenScop specification, the alias set column is a part of
172 the output columns. */
173 output = nb_subscripts + 1;
175 openscop_print_polyhedron_matrix (file, pph, output, input, locals, nb_params);
178 /* Print to FILE the powerset PDR. NB_SUBSCRIPTS is the number of subscripts
179 in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and
180 NB_PARAMS is the number of parameters in PDR. */
183 openscop_print_pdr_powerset (FILE *file,
184 ppl_Pointset_Powerset_C_Polyhedron_t ps,
190 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
192 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
193 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
195 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
196 fprintf (file, "%d\n", (int) nb_disjuncts);
198 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
199 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
200 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
201 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
203 ppl_const_Polyhedron_t ph;
205 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
206 openscop_print_pdr_polyhedron (file, ph, nb_subscripts, alias_set_dim,
210 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
211 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
214 /* Print to FILE the powerset PS in its OpenScop matrix form. */
217 openscop_print_powerset_matrix (FILE *file,
218 ppl_Pointset_Powerset_C_Polyhedron_t ps,
219 int output, int input, int locals,
223 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
225 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
226 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
228 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
229 fprintf (file, "%d\n", (int) nb_disjuncts);
231 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
232 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
233 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
234 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
236 ppl_const_Polyhedron_t ph;
238 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
239 openscop_print_polyhedron_matrix (file, ph, output, input, locals,
243 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
244 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
247 /* Prints to FILE the scattering function of PBB in OpenScop format, at some
251 openscop_print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
254 ppl_const_Polyhedron_t ph;
258 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
259 fprintf (file, "#eq");
261 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
262 fprintf (file, " s%d", (int) i);
264 for (i = 0; i < pbb_nb_local_vars (pbb); i++)
265 fprintf (file, " lv%d", (int) i);
267 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
268 fprintf (file, " i%d", (int) i);
270 for (i = 0; i < pbb_nb_params (pbb); i++)
271 fprintf (file, " p%d", (int) i);
273 fprintf (file, " cst\n");
276 /* Number of disjunct components. Remove this when
277 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
278 fprintf (file, "1\n");
280 ph = PBB_TRANSFORMED_SCATTERING (pbb)
281 ? PBB_TRANSFORMED_SCATTERING (pbb)
282 : PBB_ORIGINAL_SCATTERING (pbb);
284 openscop_print_polyhedron_matrix (file, ph,
285 pbb_nb_scattering_transform (pbb),
286 pbb_dim_iter_domain (pbb),
287 pbb_nb_local_vars (pbb),
288 pbb_nb_params (pbb));
291 fprintf (file, "#)\n");
294 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
298 print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
304 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
305 fprintf (file, "#eq");
307 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
308 fprintf (file, " s%d", (int) i);
310 for (i = 0; i < pbb_nb_local_vars (pbb); i++)
311 fprintf (file, " lv%d", (int) i);
313 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
314 fprintf (file, " i%d", (int) i);
316 for (i = 0; i < pbb_nb_params (pbb); i++)
317 fprintf (file, " p%d", (int) i);
319 fprintf (file, " cst\n");
322 /* Number of disjunct components. Remove this when
323 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
324 fprintf (file, "1\n");
325 ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb)
326 ? PBB_TRANSFORMED_SCATTERING (pbb)
327 : PBB_ORIGINAL_SCATTERING (pbb));
330 fprintf (file, "#)\n");
333 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
337 print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity)
339 if (!PBB_TRANSFORMED (pbb))
342 if (PBB_TRANSFORMED_SCATTERING (pbb)
343 || PBB_ORIGINAL_SCATTERING (pbb))
346 fprintf (file, "# Scattering function is provided\n");
348 fprintf (file, "1\n");
353 fprintf (file, "# Scattering function is not provided\n");
355 fprintf (file, "0\n");
359 openscop_print_scattering_function_1 (file, pbb, verbosity);
362 fprintf (file, "# Scattering names are not provided\n");
364 fprintf (file, "0\n");
368 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
372 print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity)
374 print_pbb_domain (file, pbb, verbosity);
377 /* Prints to FILE the scattering functions of every PBB of SCOP. */
380 print_scattering_functions (FILE *file, scop_p scop, int verbosity)
385 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
386 print_scattering_function (file, pbb, verbosity);
389 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
393 print_iteration_domains (FILE *file, scop_p scop, int verbosity)
398 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
399 print_iteration_domain (file, pbb, verbosity);
402 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
406 debug_scattering_function (poly_bb_p pbb, int verbosity)
408 print_scattering_function (stderr, pbb, verbosity);
411 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
415 debug_iteration_domain (poly_bb_p pbb, int verbosity)
417 print_iteration_domain (stderr, pbb, verbosity);
420 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
421 some VERBOSITY level. */
424 debug_scattering_functions (scop_p scop, int verbosity)
426 print_scattering_functions (stderr, scop, verbosity);
429 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
430 some VERBOSITY level. */
433 debug_iteration_domains (scop_p scop, int verbosity)
435 print_iteration_domains (stderr, scop, verbosity);
438 /* Read N integer from FILE. */
441 openscop_read_N_int (FILE *file, int N)
443 char s[OPENSCOP_MAX_STRING];
445 int i, *res = (int *) xmalloc (OPENSCOP_MAX_STRING * sizeof (int));
447 /* Skip blank and commented lines. */
448 while (fgets (s, sizeof s, file) == (char *) 0
455 for (i = 0; i < N; i++)
457 sscanf (str, "%d", &res[i]);
459 /* Jump the integer that was read. */
460 while ((*str) && !ISSPACE (*str) && (*str != '#'))
464 while ((*str) && ISSPACE (*str) && (*str != '#'))
471 /* Read one integer from FILE. */
474 openscop_read_one_int (FILE *file)
476 int *x = openscop_read_N_int (file, 1);
483 /* Read N string from FILE. */
486 openscop_read_N_string (FILE *file, int N)
489 char str[OPENSCOP_MAX_STRING];
490 char *tmp = (char *) xmalloc (sizeof (char) * OPENSCOP_MAX_STRING);
493 /* Skip blank and commented lines. */
494 while (fgets (str, sizeof str, file) == (char *) 0
502 for (i = 0; i < N; i++)
504 /* Read the first word. */
505 for (; (*s) && (!ISSPACE (*s)) && (*s != '#'); ++count)
512 while ((*s) && ISSPACE (*s) && (*s != '#'))
521 /* Read one string from FILE. */
524 openscop_read_one_string (FILE *file)
526 return openscop_read_N_string (file, 1);
529 /* Read from FILE the powerset PS in its OpenScop matrix form. OUTPUT is the
530 number of output dimensions, INPUT is the number of input dimensions,
531 LOCALS is the number of existentially quantified variables and PARAMS is
532 the number of parameters. */
535 openscop_read_powerset_matrix (FILE *file,
536 ppl_Pointset_Powerset_C_Polyhedron_t *ps,
537 int *output, int *input, int *locals,
542 nb_disjuncts = openscop_read_one_int (file);
544 for (i = 0; i < nb_disjuncts; i++)
548 openscop_read_polyhedron_matrix (file, &ph, output, input, locals,
553 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (ps, ph);
555 ppl_Pointset_Powerset_C_Polyhedron_add_disjunct (*ps, ph);
559 /* Read a scattering function from FILE and save it to PBB. Return whether
560 the scattering function was provided or not. */
563 graphite_read_scatt (FILE *file, poly_bb_p pbb)
565 bool scattering_provided = false;
566 int output, input, locals, params;
567 ppl_Polyhedron_t newp;
569 if (openscop_read_one_int (file) > 0)
571 /* Read number of disjunct components. */
572 openscop_read_one_int (file);
574 /* Read scattering function. */
575 openscop_read_polyhedron_matrix (file, &newp, &output, &input,
577 store_scattering (PBB_SCOP (pbb));
578 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
579 PBB_TRANSFORMED_SCATTERING (pbb) = newp;
580 PBB_NB_LOCAL_VARIABLES (pbb) = locals;
582 /* New scattering dimension. */
583 PBB_NB_SCATTERING_TRANSFORM (pbb) = output;
585 scattering_provided = true;
588 return scattering_provided;
591 /* Read a scop file. Return true if the scop is transformed. */
594 graphite_read_scop_file (FILE *file, scop_p scop)
596 char *tmp, *language;
597 size_t i, j, nb_statements, nbr, nbw;
598 int input, output, locals, params;
599 ppl_Pointset_Powerset_C_Polyhedron_t ps;
601 bool transform_done = false;
603 /* Ensure that the file is in OpenScop format. */
604 tmp = openscop_read_N_string (file, 2);
606 if (strcmp (tmp, "SCoP 1"))
608 error ("the file is not in OpenScop format");
614 /* Read the language. */
615 language = openscop_read_one_string (file);
617 if (strcmp (language, "Gimple"))
619 error ("the language is not recognized");
625 /* Read the context but do not use it. */
626 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, ¶ms);
628 if ((size_t) params != scop->nb_params)
630 error ("parameters number in the scop file is different from the"
631 " internal scop parameter number");
635 /* Read parameter names if provided. */
636 if (openscop_read_one_int (file))
637 openscop_read_N_string (file, scop->nb_params);
639 nb_statements = openscop_read_one_int (file);
641 if (nb_statements != VEC_length (poly_bb_p, SCOP_BBS (scop)))
643 error ("number of statements in the OpenScop file does not match"
644 " the graphite internal statements number");
648 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
650 /* Read iteration domain. */
651 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
654 /* Read scattering. */
655 transform_done = graphite_read_scatt (file, pbb);
657 /* Scattering names. */
658 openscop_read_one_int (file);
660 /* Read access functions. */
661 if (openscop_read_one_int (file) > 0)
663 nbr = openscop_read_one_int (file);
665 /* Read access functions. */
666 for (j = 0; j < nbr; j++)
667 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
670 nbw = openscop_read_one_int (file);
672 /* Write access functions. */
673 for (j = 0; j < nbw; j++)
674 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
678 /* Statement body. */
679 openscop_read_one_int (file);
682 return transform_done;
685 /* Initialize and return a file that will be used to write a scop. SCOP_NUMBER
686 is a sequential number (identifier) used to differentiate scop files.
687 Examples of the generated file names: dump_base_name.0.graphite,
688 dump_base_name.1.graphite, dump_base_name.2.graphite, etc. */
691 init_graphite_out_file (int scop_number)
693 FILE *graphite_out_file;
694 int len = strlen (dump_base_name);
695 char *dumpname = XNEWVEC (char, len + 25);
696 char *s_scop_number = XNEWVEC (char, 15);
698 memcpy (dumpname, dump_base_name, len + 1);
699 strip_off_ending (dumpname, len);
700 sprintf (s_scop_number, ".%d", scop_number);
701 strcat (dumpname, s_scop_number);
702 strcat (dumpname, ".graphite");
703 graphite_out_file = fopen (dumpname, "w+b");
705 if (graphite_out_file == 0)
706 fatal_error ("can%'t open %s for writing: %m", dumpname);
710 return graphite_out_file;
713 /* Open and return a file used for scop reading. SCOP_NUMBER is a sequential
714 number (identifier) used to differentiate scop files. Examples of the
715 generated file names: dump_base_name.0.graphite, dump_base_name.1.graphite,
716 dump_base_name.2.graphite, etc. */
719 init_graphite_in_file (int scop_number)
721 FILE *graphite_in_file;
722 int len = strlen (dump_base_name);
723 char *dumpname = XNEWVEC (char, len + 25);
724 char *s_scop_number = XNEWVEC (char, 15);
726 memcpy (dumpname, dump_base_name, len + 1);
727 strip_off_ending (dumpname, len);
728 sprintf (s_scop_number, ".%d", scop_number);
729 strcat (dumpname, s_scop_number);
730 strcat (dumpname, ".graphite");
731 graphite_in_file = fopen (dumpname, "r+b");
733 if (graphite_in_file == 0)
734 fatal_error ("can%'t open %s for reading: %m", dumpname);
738 return graphite_in_file;
741 /* Apply graphite transformations to all the basic blocks of SCOP. */
744 apply_poly_transforms (scop_p scop)
746 bool transform_done = false;
748 static size_t file_scop_number = 0;
750 /* This feature is only enabled in the Graphite branch. */
753 graphite_file = init_graphite_in_file (file_scop_number);
754 transform_done |= graphite_read_scop_file (graphite_file, scop);
756 if (!graphite_legal_transform (scop))
757 fatal_error ("the graphite file read for scop %d does not contain a legal transform",
758 (int) file_scop_number);
763 /* Generate code even if we did not apply any real transformation.
764 This also allows to check the performance for the identity
765 transformation: GIMPLE -> GRAPHITE -> GIMPLE
766 Keep in mind that CLooG optimizes in control, so the loop structure
767 may change, even if we only use -fgraphite-identity. */
768 if (flag_graphite_identity)
769 transform_done = true;
771 if (flag_loop_parallelize_all)
772 transform_done = true;
775 transform_done |= scop_do_block (scop);
778 if (flag_loop_strip_mine)
779 transform_done |= scop_do_strip_mine (scop);
781 if (flag_loop_interchange)
782 transform_done |= scop_do_interchange (scop);
785 if (flag_loop_flatten)
786 transform_done |= flatten_all_loops (scop);
788 /* This feature is only enabled in the Graphite branch. */
791 graphite_file = init_graphite_out_file (file_scop_number);
792 print_scop (graphite_file, scop, 1);
796 return transform_done;
799 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
800 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */
803 can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2)
806 ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff;
808 if (PDR_PBB (pdr1) != PDR_PBB (pdr2)
809 || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
810 || PDR_TYPE (pdr1) != PDR_TYPE (pdr2))
813 af1 = PDR_ACCESSES (pdr1);
814 af2 = PDR_ACCESSES (pdr2);
815 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
817 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2);
819 res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff);
820 ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
824 /* Removes duplicated data references in PBB. */
827 pbb_remove_duplicate_pdrs (poly_bb_p pbb)
830 poly_dr_p pdr1, pdr2;
831 unsigned n = VEC_length (poly_dr_p, PBB_DRS (pbb));
832 VEC (poly_dr_p, heap) *collapsed = VEC_alloc (poly_dr_p, heap, n);
834 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1)
835 FOR_EACH_VEC_ELT (poly_dr_p, collapsed, j, pdr2)
836 if (!can_collapse_pdrs (pdr1, pdr2))
837 VEC_quick_push (poly_dr_p, collapsed, pdr1);
839 VEC_free (poly_dr_p, heap, collapsed);
840 PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
843 /* Create a new polyhedral data reference and add it to PBB. It is
844 defined by its ACCESSES, its TYPE, and the number of subscripts
848 new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
849 ppl_Pointset_Powerset_C_Polyhedron_t accesses,
850 enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
853 poly_dr_p pdr = XNEW (struct poly_dr);
856 PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
857 PDR_NB_REFS (pdr) = 1;
859 PDR_ACCESSES (pdr) = accesses;
860 PDR_TYPE (pdr) = type;
862 PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
863 VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
866 /* Free polyhedral data reference PDR. */
869 free_poly_dr (poly_dr_p pdr)
871 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
875 /* Create a new polyhedral black box. */
878 new_poly_bb (scop_p scop, void *black_box, bool reduction)
880 poly_bb_p pbb = XNEW (struct poly_bb);
882 PBB_DOMAIN (pbb) = NULL;
883 PBB_SCOP (pbb) = scop;
884 pbb_set_black_box (pbb, black_box);
885 PBB_TRANSFORMED (pbb) = NULL;
886 PBB_SAVED (pbb) = NULL;
887 PBB_ORIGINAL (pbb) = NULL;
888 PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
889 PBB_IS_REDUCTION (pbb) = reduction;
890 PBB_PDR_DUPLICATES_REMOVED (pbb) = false;
891 VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
894 /* Free polyhedral black box. */
897 free_poly_bb (poly_bb_p pbb)
902 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
904 if (PBB_TRANSFORMED (pbb))
905 poly_scattering_free (PBB_TRANSFORMED (pbb));
908 poly_scattering_free (PBB_SAVED (pbb));
910 if (PBB_ORIGINAL (pbb))
911 poly_scattering_free (PBB_ORIGINAL (pbb));
914 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
917 VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
922 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr)
926 fprintf (file, "# eq");
928 fprintf (file, " alias");
930 for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
931 fprintf (file, " sub%d", (int) i);
933 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
934 fprintf (file, " i%d", (int) i);
936 for (i = 0; i < pbb_nb_params (pbb); i++)
937 fprintf (file, " p%d", (int) i);
939 fprintf (file, " cst\n");
942 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
946 print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
952 fprintf (file, "# pdr_%d (", PDR_ID (pdr));
954 switch (PDR_TYPE (pdr))
957 fprintf (file, "read \n");
961 fprintf (file, "write \n");
965 fprintf (file, "may_write \n");
972 dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
977 fprintf (file, "# data accesses (\n");
978 print_pdr_access_layout (file, PDR_PBB (pdr), pdr);
981 alias_set_dim = pdr_alias_set_dim (pdr) + 1;
983 openscop_print_pdr_powerset (file,
985 PDR_NB_SUBSCRIPTS (pdr),
987 pbb_nb_params (PDR_PBB (pdr)));
990 fprintf (file, "#)\n");
993 fprintf (file, "#)\n");
996 /* Prints to STDERR the polyhedral data reference PDR, at some
1000 debug_pdr (poly_dr_p pdr, int verbosity)
1002 print_pdr (stderr, pdr, verbosity);
1005 /* Creates a new SCOP containing REGION. */
1008 new_scop (void *region)
1010 scop_p scop = XNEW (struct scop);
1012 SCOP_CONTEXT (scop) = NULL;
1013 scop_set_region (scop, region);
1014 SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
1015 SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
1016 eq_poly_ddr_p, free_poly_ddr);
1017 SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
1018 SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
1019 SCOP_SAVED_SCHEDULE (scop) = NULL;
1020 POLY_SCOP_P (scop) = false;
1028 free_scop (scop_p scop)
1033 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1036 VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
1038 if (SCOP_CONTEXT (scop))
1039 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
1041 htab_delete (SCOP_ORIGINAL_PDDRS (scop));
1042 free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
1043 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1044 free_lst (SCOP_SAVED_SCHEDULE (scop));
1048 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
1052 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1055 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1057 if (!PBB_DOMAIN (pbb))
1062 fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1063 fprintf (file, "#eq");
1065 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1066 fprintf (file, " i%d", (int) i);
1068 for (i = 0; i < pbb_nb_params (pbb); i++)
1069 fprintf (file, " p%d", (int) i);
1071 fprintf (file, " cst\n");
1074 if (PBB_DOMAIN (pbb))
1075 openscop_print_powerset_matrix (file, PBB_DOMAIN (pbb),
1076 pbb_dim_iter_domain (pbb),
1079 pbb_nb_params (pbb));
1081 fprintf (file, "0\n");
1084 fprintf (file, "#)\n");
1087 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
1090 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1093 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1095 if (!PBB_DOMAIN (pbb))
1100 fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1101 fprintf (file, "# eq");
1103 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1104 fprintf (file, " i%d", (int) i);
1106 for (i = 0; i < pbb_nb_params (pbb); i++)
1107 fprintf (file, " p%d", (int) i);
1109 fprintf (file, " cst\n");
1112 if (PBB_DOMAIN (pbb))
1113 ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
1115 fprintf (file, "0\n");
1118 fprintf (file, "#)\n");
1121 /* Dump the cases of a graphite basic block GBB on FILE. */
1124 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
1128 VEC (gimple, heap) *cases;
1133 cases = GBB_CONDITION_CASES (gbb);
1134 if (VEC_empty (gimple, cases))
1137 fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
1139 FOR_EACH_VEC_ELT (gimple, cases, i, stmt)
1141 fprintf (file, "# ");
1142 print_gimple_stmt (file, stmt, 0, 0);
1145 fprintf (file, "#)\n");
1148 /* Dump conditions of a graphite basic block GBB on FILE. */
1151 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
1155 VEC (gimple, heap) *conditions;
1160 conditions = GBB_CONDITIONS (gbb);
1161 if (VEC_empty (gimple, conditions))
1164 fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
1166 FOR_EACH_VEC_ELT (gimple, conditions, i, stmt)
1168 fprintf (file, "# ");
1169 print_gimple_stmt (file, stmt, 0, 0);
1172 fprintf (file, "#)\n");
1175 /* Print to FILE all the data references of PBB, at some VERBOSITY
1179 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
1186 if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0)
1189 fprintf (file, "# Access informations are not provided\n");\
1190 fprintf (file, "0\n");
1195 fprintf (file, "# Data references (\n");
1198 fprintf (file, "# Access informations are provided\n");
1199 fprintf (file, "1\n");
1201 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1202 if (PDR_TYPE (pdr) == PDR_READ)
1208 fprintf (file, "# Read data references (\n");
1211 fprintf (file, "# Read access informations\n");
1212 fprintf (file, "%d\n", nb_reads);
1214 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1215 if (PDR_TYPE (pdr) == PDR_READ)
1216 print_pdr (file, pdr, verbosity);
1219 fprintf (file, "#)\n");
1222 fprintf (file, "# Write data references (\n");
1225 fprintf (file, "# Write access informations\n");
1226 fprintf (file, "%d\n", nb_writes);
1228 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1229 if (PDR_TYPE (pdr) != PDR_READ)
1230 print_pdr (file, pdr, verbosity);
1233 fprintf (file, "#)\n");
1236 fprintf (file, "#)\n");
1239 /* Print to STDERR all the data references of PBB. */
1242 debug_pdrs (poly_bb_p pbb, int verbosity)
1244 print_pdrs (stderr, pbb, verbosity);
1247 /* Print to FILE the body of PBB, at some VERBOSITY level.
1248 If statement_body_provided is false statement body is not printed. */
1251 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity,
1252 bool statement_body_provided)
1255 fprintf (file, "# Body (\n");
1257 if (!statement_body_provided)
1260 fprintf (file, "# Statement body is not provided\n");
1262 fprintf (file, "0\n");
1265 fprintf (file, "#)\n");
1270 fprintf (file, "# Statement body is provided\n");
1271 fprintf (file, "1\n");
1274 fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
1277 fprintf (file, "# Statement body\n");
1279 fprintf (file, "{\n");
1280 dump_bb (pbb_bb (pbb), file, 0);
1281 fprintf (file, "}\n");
1284 fprintf (file, "#)\n");
1287 /* Print to FILE the domain and scattering function of PBB, at some
1291 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
1295 fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1296 dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
1297 dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
1300 openscop_print_pbb_domain (file, pbb, verbosity);
1301 print_scattering_function (file, pbb, verbosity);
1302 print_pdrs (file, pbb, verbosity);
1303 print_pbb_body (file, pbb, verbosity, false);
1306 fprintf (file, "#)\n");
1309 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
1312 print_scop_params (FILE *file, scop_p scop, int verbosity)
1318 fprintf (file, "# parameters (\n");
1320 if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
1323 fprintf (file, "# Parameter names are provided\n");
1325 fprintf (file, "1\n");
1328 fprintf (file, "# Parameter names\n");
1333 fprintf (file, "# Parameter names are not provided\n");
1334 fprintf (file, "0\n");
1337 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t)
1339 print_generic_expr (file, t, 0);
1340 fprintf (file, " ");
1343 fprintf (file, "\n");
1346 fprintf (file, "#)\n");
1349 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1353 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
1359 fprintf (file, "# Context (\n");
1360 fprintf (file, "#eq");
1362 for (i = 0; i < scop_nb_params (scop); i++)
1363 fprintf (file, " p%d", (int) i);
1365 fprintf (file, " cst\n");
1368 if (SCOP_CONTEXT (scop))
1369 openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0,
1370 scop_nb_params (scop));
1372 fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
1373 (int) scop_nb_params (scop));
1376 fprintf (file, "# )\n");
1379 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
1382 print_scop_context (FILE *file, scop_p scop, int verbosity)
1388 fprintf (file, "# Context (\n");
1389 fprintf (file, "#eq");
1391 for (i = 0; i < scop_nb_params (scop); i++)
1392 fprintf (file, " p%d", (int) i);
1394 fprintf (file, " cst\n");
1397 if (SCOP_CONTEXT (scop))
1398 ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
1400 fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
1403 fprintf (file, "# )\n");
1406 /* Print to FILE the SCOP, at some VERBOSITY level. */
1409 print_scop (FILE *file, scop_p scop, int verbosity)
1414 fprintf (file, "SCoP 1\n#(\n");
1415 fprintf (file, "# Language\nGimple\n");
1416 openscop_print_scop_context (file, scop, verbosity);
1417 print_scop_params (file, scop, verbosity);
1420 fprintf (file, "# Number of statements\n");
1422 fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop)));
1424 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1425 print_pbb (file, pbb, verbosity);
1429 fprintf (file, "# original_lst (\n");
1430 print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
1431 fprintf (file, "\n#)\n");
1433 fprintf (file, "# transformed_lst (\n");
1434 print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
1435 fprintf (file, "\n#)\n");
1438 fprintf (file, "#)\n");
1441 /* Print to FILE the input file that CLooG would expect as input, at
1442 some VERBOSITY level. */
1445 print_cloog (FILE *file, scop_p scop, int verbosity)
1450 fprintf (file, "# SCoP (generated by GCC/Graphite\n");
1452 fprintf (file, "# CLooG output language\n");
1453 fprintf (file, "c\n");
1455 print_scop_context (file, scop, verbosity);
1456 print_scop_params (file, scop, verbosity);
1459 fprintf (file, "# Number of statements\n");
1461 fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1463 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1466 fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1468 print_pbb_domain (file, pbb, verbosity);
1469 fprintf (file, "0 0 0");
1472 fprintf (file, "# For future CLooG options.\n");
1474 fprintf (file, "\n");
1477 fprintf (file, "#)\n");
1480 fprintf (file, "0");
1482 fprintf (file, "# Don't set the iterator names.\n");
1484 fprintf (file, "\n");
1487 fprintf (file, "# Number of scattering functions\n");
1489 fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1490 unify_scattering_dimensions (scop);
1492 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1494 if (!PBB_TRANSFORMED (pbb)
1495 || !(PBB_TRANSFORMED_SCATTERING (pbb)
1496 || PBB_ORIGINAL_SCATTERING (pbb)))
1500 fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1502 print_scattering_function_1 (file, pbb, verbosity);
1505 fprintf (file, "#)\n");
1508 fprintf (file, "0");
1510 fprintf (file, "# Don't set the scattering dimension names.\n");
1512 fprintf (file, "\n");
1514 fprintf (file, "#)\n");
1517 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
1520 debug_pbb_domain (poly_bb_p pbb, int verbosity)
1522 print_pbb_domain (stderr, pbb, verbosity);
1525 /* Print to FILE the domain and scattering function of PBB, at some
1529 debug_pbb (poly_bb_p pbb, int verbosity)
1531 print_pbb (stderr, pbb, verbosity);
1534 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
1537 debug_scop_context (scop_p scop, int verbosity)
1539 print_scop_context (stderr, scop, verbosity);
1542 /* Print to STDERR the SCOP, at some VERBOSITY level. */
1545 debug_scop (scop_p scop, int verbosity)
1547 print_scop (stderr, scop, verbosity);
1550 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1554 debug_cloog (scop_p scop, int verbosity)
1556 print_cloog (stderr, scop, verbosity);
1559 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1563 debug_scop_params (scop_p scop, int verbosity)
1565 print_scop_params (stderr, scop, verbosity);
1569 /* The dimension in the transformed scattering polyhedron of PBB
1570 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
1573 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
1575 ppl_const_Constraint_System_t pcs;
1576 ppl_Constraint_System_const_iterator_t cit, cend;
1577 ppl_const_Constraint_t cstr;
1578 ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1579 ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
1580 ppl_Linear_Expression_t expr;
1581 ppl_Coefficient_t coef;
1586 ppl_new_Coefficient (&coef);
1587 ppl_Polyhedron_get_constraints (ph, &pcs);
1588 ppl_new_Constraint_System_const_iterator (&cit);
1589 ppl_new_Constraint_System_const_iterator (&cend);
1591 for (ppl_Constraint_System_begin (pcs, cit),
1592 ppl_Constraint_System_end (pcs, cend);
1593 !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
1594 ppl_Constraint_System_const_iterator_increment (cit))
1596 ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
1597 ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
1598 ppl_Linear_Expression_coefficient (expr, iter, coef);
1599 ppl_Coefficient_to_mpz_t (coef, val);
1601 if (mpz_sgn (val) == 0)
1603 ppl_delete_Linear_Expression (expr);
1607 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
1609 ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
1611 ppl_Linear_Expression_coefficient (expr, scatter, coef);
1612 ppl_Coefficient_to_mpz_t (coef, val);
1614 if (mpz_sgn (val) != 0)
1617 ppl_delete_Linear_Expression (expr);
1618 ppl_delete_Coefficient (coef);
1619 ppl_delete_Constraint_System_const_iterator (cit);
1620 ppl_delete_Constraint_System_const_iterator (cend);
1630 /* Returns the number of iterations RES of the loop around PBB at
1631 time(scattering) dimension TIME_DEPTH. */
1634 pbb_number_of_iterations_at_time (poly_bb_p pbb,
1635 graphite_dim_t time_depth,
1638 ppl_Pointset_Powerset_C_Polyhedron_t domain, sctr_lb, sctr_ub;
1639 ppl_dimension_type domain_dim, sctr_dim;
1640 graphite_dim_t dim_iter_domain = pbb_dim_iter_domain (pbb);
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);
1656 mpz_set_si (one, 1);
1658 /* Compute the upper bound on the original iteration domain and add
1659 that upper bound to the scattering. */
1660 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1661 (&sctr_ub, PBB_TRANSFORMED_SCATTERING (pbb));
1662 for (i = 0; i < (int) dim_iter_domain; i++)
1664 ppl_Linear_Expression_t eq;
1665 ppl_Constraint_t pc;
1666 ppl_Constraint_System_t cs;
1667 ppl_Polyhedron_t ph;
1668 ppl_Pointset_Powerset_C_Polyhedron_t pph;
1670 ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1671 ppl_set_coef (le, i, 1);
1672 ppl_min_for_le_pointset (domain, le, lb);
1673 ppl_max_for_le_pointset (domain, le, ub);
1674 mpz_sub (diff, ub, lb);
1675 mpz_add (diff, diff, one);
1677 ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1678 ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1679 ppl_set_inhomogeneous_gmp (eq, diff);
1681 ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1682 ppl_new_Constraint_System_from_Constraint (&cs, pc);
1683 ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1684 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1685 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub, pph);
1687 ppl_delete_Linear_Expression (le);
1688 ppl_delete_Linear_Expression (eq);
1689 ppl_delete_Polyhedron (ph);
1690 ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1691 ppl_delete_Constraint (pc);
1692 ppl_delete_Constraint_System (cs);
1695 /* Compute the lower bound on the original iteration domain and add
1696 it to the scattering. */
1697 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1698 (&sctr_lb, PBB_TRANSFORMED_SCATTERING (pbb));
1699 for (i = 0; i < (int) dim_iter_domain; i++)
1701 ppl_Linear_Expression_t eq;
1702 ppl_Constraint_t pc;
1703 ppl_Constraint_System_t cs;
1704 ppl_Polyhedron_t ph;
1705 ppl_Pointset_Powerset_C_Polyhedron_t pph;
1707 ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1708 ppl_set_coef (le, i, 1);
1709 ppl_min_for_le_pointset (domain, le, lb);
1711 ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1712 ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1713 ppl_set_inhomogeneous_gmp (eq, lb);
1715 ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1716 ppl_new_Constraint_System_from_Constraint (&cs, pc);
1717 ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1718 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1719 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb, pph);
1721 ppl_delete_Linear_Expression (le);
1722 ppl_delete_Linear_Expression (eq);
1723 ppl_delete_Polyhedron (ph);
1724 ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1725 ppl_delete_Constraint (pc);
1726 ppl_delete_Constraint_System (cs);
1729 /* Extract the number of iterations. */
1730 ppl_new_Linear_Expression_with_dimension (&le, sctr_dim);
1731 ppl_set_coef (le, time_depth, 1);
1732 ppl_min_for_le_pointset (sctr_lb, le, lb);
1733 ppl_max_for_le_pointset (sctr_ub, le, ub);
1734 mpz_sub (res, ub, lb);
1740 ppl_delete_Linear_Expression (le);
1741 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub);
1742 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb);
1743 ppl_delete_Pointset_Powerset_C_Polyhedron (domain);
1746 /* Translates LOOP to LST. */
1749 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
1752 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1754 for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
1757 basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1759 if (bb->loop_father == loop)
1760 stmt = new_lst_stmt (pbb);
1761 else if (flow_bb_inside_loop_p (loop, bb))
1763 loop_p next = loop->inner;
1765 while (next && !flow_bb_inside_loop_p (next, bb))
1768 stmt = loop_to_lst (next, bbs, i);
1773 return new_lst_loop (seq);
1776 VEC_safe_push (lst_p, heap, seq, stmt);
1779 return new_lst_loop (seq);
1782 /* Reads the original scattering of the SCOP and returns an LST
1786 scop_to_lst (scop_p scop)
1789 int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1790 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1791 sese region = SCOP_REGION (scop);
1793 for (i = 0; i < n; i++)
1795 poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1796 loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1798 if (loop_in_sese_p (loop, region))
1799 res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1801 res = new_lst_stmt (pbb);
1803 VEC_safe_push (lst_p, heap, seq, res);
1806 res = new_lst_loop (seq);
1807 SCOP_ORIGINAL_SCHEDULE (scop) = res;
1808 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1811 /* Print to FILE on a new line COLUMN white spaces. */
1814 lst_indent_to (FILE *file, int column)
1819 fprintf (file, "\n#");
1821 for (i = 0; i < column; i++)
1822 fprintf (file, " ");
1825 /* Print LST to FILE with INDENT spaces of indentation. */
1828 print_lst (FILE *file, lst_p lst, int indent)
1833 lst_indent_to (file, indent);
1835 if (LST_LOOP_P (lst))
1840 if (LST_LOOP_FATHER (lst))
1841 fprintf (file, "%d (loop", lst_dewey_number (lst));
1843 fprintf (file, "#(root");
1845 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1846 print_lst (file, l, indent + 2);
1848 fprintf (file, ")");
1851 fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1854 /* Print LST to STDERR. */
1857 debug_lst (lst_p lst)
1859 print_lst (stderr, lst, 0);
1862 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1865 dot_lst_1 (FILE *file, lst_p lst)
1870 if (LST_LOOP_P (lst))
1875 if (!LST_LOOP_FATHER (lst))
1876 fprintf (file, "L -> L_%d_%d\n",
1878 lst_dewey_number (lst));
1880 fprintf (file, "L_%d_%d -> L_%d_%d\n",
1881 lst_depth (LST_LOOP_FATHER (lst)),
1882 lst_dewey_number (LST_LOOP_FATHER (lst)),
1884 lst_dewey_number (lst));
1886 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1887 dot_lst_1 (file, l);
1891 fprintf (file, "L_%d_%d -> S_%d\n",
1892 lst_depth (LST_LOOP_FATHER (lst)),
1893 lst_dewey_number (LST_LOOP_FATHER (lst)),
1894 pbb_index (LST_PBB (lst)));
1898 /* Display the LST using dotty. */
1903 /* When debugging, enable the following code. This cannot be used
1904 in production compilers because it calls "system". */
1906 FILE *stream = fopen ("/tmp/lst.dot", "w");
1907 gcc_assert (stream);
1909 fputs ("digraph all {\n", stream);
1910 dot_lst_1 (stream, lst);
1911 fputs ("}\n\n", stream);
1914 system ("dotty /tmp/lst.dot &");
1916 fputs ("digraph all {\n", stderr);
1917 dot_lst_1 (stderr, lst);
1918 fputs ("}\n\n", stderr);
1923 /* Computes a checksum for the code generated by CLooG for SCOP. */
1926 cloog_checksum (scop_p scop ATTRIBUTE_UNUSED)
1928 /* When debugging, enable the following code. This cannot be used
1929 in production compilers because it calls "system". */
1931 FILE *stream = fopen ("/tmp/scop.cloog", "w");
1932 gcc_assert (stream);
1933 print_cloog (stream, scop, 0);
1936 fputs ("\n", stdout);
1937 system ("cloog -compilable 1 /tmp/scop.cloog > /tmp/scop.c ; gcc -O0 -g /tmp/scop.c -lm -o /tmp/scop; /tmp/scop | md5sum ");