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 (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
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 (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
134 max_scattering
= MAX (pbb_nb_scattering_transform (pbb
), max_scattering
);
136 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
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 (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
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 (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
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
;
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 /* Apply graphite transformations to all the basic blocks of SCOP. */
689 apply_poly_transforms (scop_p scop
)
691 bool transform_done
= false;
693 if (flag_graphite_read
)
695 transform_done
|= graphite_read_scop_file (graphite_in_file
, scop
);
696 gcc_assert (graphite_legal_transform (scop
));
699 /* Generate code even if we did not apply any real transformation.
700 This also allows to check the performance for the identity
701 transformation: GIMPLE -> GRAPHITE -> GIMPLE
702 Keep in mind that CLooG optimizes in control, so the loop structure
703 may change, even if we only use -fgraphite-identity. */
704 if (flag_graphite_identity
)
705 transform_done
= true;
707 if (flag_loop_parallelize_all
)
708 transform_done
= true;
711 transform_done
|= scop_do_block (scop
);
714 if (flag_loop_strip_mine
)
715 transform_done
|= scop_do_strip_mine (scop
);
717 if (flag_loop_interchange
)
718 transform_done
|= scop_do_interchange (scop
);
721 if (flag_graphite_write
)
722 print_scop (graphite_out_file
, scop
, 1);
724 return transform_done
;
727 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
728 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */
731 can_collapse_pdrs (poly_dr_p pdr1
, poly_dr_p pdr2
)
734 ppl_Pointset_Powerset_C_Polyhedron_t af1
, af2
, diff
;
736 if (PDR_PBB (pdr1
) != PDR_PBB (pdr2
)
737 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
)
738 || PDR_TYPE (pdr1
) != PDR_TYPE (pdr2
))
741 af1
= PDR_ACCESSES (pdr1
);
742 af2
= PDR_ACCESSES (pdr2
);
743 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
745 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff
, af2
);
747 res
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff
);
748 ppl_delete_Pointset_Powerset_C_Polyhedron (diff
);
752 /* Removes duplicated data references in PBB. */
755 pbb_remove_duplicate_pdrs (poly_bb_p pbb
)
758 poly_dr_p pdr1
, pdr2
;
759 unsigned n
= VEC_length (poly_dr_p
, PBB_DRS (pbb
));
760 VEC (poly_dr_p
, heap
) *collapsed
= VEC_alloc (poly_dr_p
, heap
, n
);
762 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr1
); i
++)
763 for (j
= 0; VEC_iterate (poly_dr_p
, collapsed
, j
, pdr2
); j
++)
764 if (!can_collapse_pdrs (pdr1
, pdr2
))
765 VEC_quick_push (poly_dr_p
, collapsed
, pdr1
);
767 VEC_free (poly_dr_p
, heap
, collapsed
);
768 PBB_PDR_DUPLICATES_REMOVED (pbb
) = true;
771 /* Create a new polyhedral data reference and add it to PBB. It is
772 defined by its ACCESSES, its TYPE, and the number of subscripts
776 new_poly_dr (poly_bb_p pbb
, int dr_base_object_set
,
777 ppl_Pointset_Powerset_C_Polyhedron_t accesses
,
778 enum poly_dr_type type
, void *cdr
, graphite_dim_t nb_subscripts
)
781 poly_dr_p pdr
= XNEW (struct poly_dr
);
784 PDR_BASE_OBJECT_SET (pdr
) = dr_base_object_set
;
785 PDR_NB_REFS (pdr
) = 1;
787 PDR_ACCESSES (pdr
) = accesses
;
788 PDR_TYPE (pdr
) = type
;
790 PDR_NB_SUBSCRIPTS (pdr
) = nb_subscripts
;
791 VEC_safe_push (poly_dr_p
, heap
, PBB_DRS (pbb
), pdr
);
794 /* Free polyhedral data reference PDR. */
797 free_poly_dr (poly_dr_p pdr
)
799 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr
));
803 /* Create a new polyhedral black box. */
806 new_poly_bb (scop_p scop
, void *black_box
, bool reduction
)
808 poly_bb_p pbb
= XNEW (struct poly_bb
);
810 PBB_DOMAIN (pbb
) = NULL
;
811 PBB_SCOP (pbb
) = scop
;
812 pbb_set_black_box (pbb
, black_box
);
813 PBB_TRANSFORMED (pbb
) = NULL
;
814 PBB_SAVED (pbb
) = NULL
;
815 PBB_ORIGINAL (pbb
) = NULL
;
816 PBB_DRS (pbb
) = VEC_alloc (poly_dr_p
, heap
, 3);
817 PBB_IS_REDUCTION (pbb
) = reduction
;
818 PBB_PDR_DUPLICATES_REMOVED (pbb
) = false;
819 VEC_safe_push (poly_bb_p
, heap
, SCOP_BBS (scop
), pbb
);
822 /* Free polyhedral black box. */
825 free_poly_bb (poly_bb_p pbb
)
830 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb
));
832 if (PBB_TRANSFORMED (pbb
))
833 poly_scattering_free (PBB_TRANSFORMED (pbb
));
836 poly_scattering_free (PBB_SAVED (pbb
));
838 if (PBB_ORIGINAL (pbb
))
839 poly_scattering_free (PBB_ORIGINAL (pbb
));
842 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
845 VEC_free (poly_dr_p
, heap
, PBB_DRS (pbb
));
850 print_pdr_access_layout (FILE *file
, poly_bb_p pbb
, poly_dr_p pdr
)
854 fprintf (file
, "# eq");
856 fprintf (file
, " alias");
858 for (i
= 0; i
< PDR_NB_SUBSCRIPTS (pdr
); i
++)
859 fprintf (file
, " sub%d", (int) i
);
861 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
862 fprintf (file
, " i%d", (int) i
);
864 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
865 fprintf (file
, " p%d", (int) i
);
867 fprintf (file
, " cst\n");
870 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
874 print_pdr (FILE *file
, poly_dr_p pdr
, int verbosity
)
880 fprintf (file
, "# pdr_%d (", PDR_ID (pdr
));
882 switch (PDR_TYPE (pdr
))
885 fprintf (file
, "read \n");
889 fprintf (file
, "write \n");
893 fprintf (file
, "may_write \n");
900 dump_data_reference (file
, (data_reference_p
) PDR_CDR (pdr
));
905 fprintf (file
, "# data accesses (\n");
906 print_pdr_access_layout (file
, PDR_PBB (pdr
), pdr
);
909 alias_set_dim
= pdr_alias_set_dim (pdr
) + 1;
911 openscop_print_pdr_powerset (file
,
913 PDR_NB_SUBSCRIPTS (pdr
),
915 pbb_nb_params (PDR_PBB (pdr
)));
918 fprintf (file
, "#)\n");
921 fprintf (file
, "#)\n");
924 /* Prints to STDERR the polyhedral data reference PDR, at some
928 debug_pdr (poly_dr_p pdr
, int verbosity
)
930 print_pdr (stderr
, pdr
, verbosity
);
933 /* Creates a new SCOP containing REGION. */
936 new_scop (void *region
)
938 scop_p scop
= XNEW (struct scop
);
940 SCOP_CONTEXT (scop
) = NULL
;
941 scop_set_region (scop
, region
);
942 SCOP_BBS (scop
) = VEC_alloc (poly_bb_p
, heap
, 3);
943 SCOP_ORIGINAL_PDDRS (scop
) = htab_create (10, hash_poly_ddr_p
,
944 eq_poly_ddr_p
, free_poly_ddr
);
945 SCOP_ORIGINAL_SCHEDULE (scop
) = NULL
;
946 SCOP_TRANSFORMED_SCHEDULE (scop
) = NULL
;
947 SCOP_SAVED_SCHEDULE (scop
) = NULL
;
948 POLY_SCOP_P (scop
) = false;
956 free_scop (scop_p scop
)
961 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
964 VEC_free (poly_bb_p
, heap
, SCOP_BBS (scop
));
966 if (SCOP_CONTEXT (scop
))
967 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop
));
969 htab_delete (SCOP_ORIGINAL_PDDRS (scop
));
970 free_lst (SCOP_ORIGINAL_SCHEDULE (scop
));
971 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
972 free_lst (SCOP_SAVED_SCHEDULE (scop
));
976 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
980 openscop_print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
983 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
985 if (!PBB_DOMAIN (pbb
))
990 fprintf (file
, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
991 fprintf (file
, "#eq");
993 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
994 fprintf (file
, " i%d", (int) i
);
996 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
997 fprintf (file
, " p%d", (int) i
);
999 fprintf (file
, " cst\n");
1002 if (PBB_DOMAIN (pbb
))
1003 openscop_print_powerset_matrix (file
, PBB_DOMAIN (pbb
),
1004 pbb_dim_iter_domain (pbb
),
1007 pbb_nb_params (pbb
));
1009 fprintf (file
, "0\n");
1012 fprintf (file
, "#)\n");
1015 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
1018 print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
1021 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1023 if (!PBB_DOMAIN (pbb
))
1028 fprintf (file
, "# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
1029 fprintf (file
, "# eq");
1031 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
1032 fprintf (file
, " i%d", (int) i
);
1034 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
1035 fprintf (file
, " p%d", (int) i
);
1037 fprintf (file
, " cst\n");
1040 if (PBB_DOMAIN (pbb
))
1041 ppl_print_powerset_matrix (file
, PBB_DOMAIN (pbb
));
1043 fprintf (file
, "0\n");
1046 fprintf (file
, "#)\n");
1049 /* Dump the cases of a graphite basic block GBB on FILE. */
1052 dump_gbb_cases (FILE *file
, gimple_bb_p gbb
)
1056 VEC (gimple
, heap
) *cases
;
1061 cases
= GBB_CONDITION_CASES (gbb
);
1062 if (VEC_empty (gimple
, cases
))
1065 fprintf (file
, "# cases bb_%d (\n", GBB_BB (gbb
)->index
);
1067 for (i
= 0; VEC_iterate (gimple
, cases
, i
, stmt
); i
++)
1069 fprintf (file
, "# ");
1070 print_gimple_stmt (file
, stmt
, 0, 0);
1073 fprintf (file
, "#)\n");
1076 /* Dump conditions of a graphite basic block GBB on FILE. */
1079 dump_gbb_conditions (FILE *file
, gimple_bb_p gbb
)
1083 VEC (gimple
, heap
) *conditions
;
1088 conditions
= GBB_CONDITIONS (gbb
);
1089 if (VEC_empty (gimple
, conditions
))
1092 fprintf (file
, "# conditions bb_%d (\n", GBB_BB (gbb
)->index
);
1094 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1096 fprintf (file
, "# ");
1097 print_gimple_stmt (file
, stmt
, 0, 0);
1100 fprintf (file
, "#)\n");
1103 /* Print to FILE all the data references of PBB, at some VERBOSITY
1107 print_pdrs (FILE *file
, poly_bb_p pbb
, int verbosity
)
1114 if (VEC_length (poly_dr_p
, PBB_DRS (pbb
)) == 0)
1117 fprintf (file
, "# Access informations are not provided\n");\
1118 fprintf (file
, "0\n");
1123 fprintf (file
, "# Data references (\n");
1126 fprintf (file
, "# Access informations are provided\n");
1127 fprintf (file
, "1\n");
1129 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
1130 if (PDR_TYPE (pdr
) == PDR_READ
)
1136 fprintf (file
, "# Read data references (\n");
1139 fprintf (file
, "# Read access informations\n");
1140 fprintf (file
, "%d\n", nb_reads
);
1142 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
1143 if (PDR_TYPE (pdr
) == PDR_READ
)
1144 print_pdr (file
, pdr
, verbosity
);
1147 fprintf (file
, "#)\n");
1150 fprintf (file
, "# Write data references (\n");
1153 fprintf (file
, "# Write access informations\n");
1154 fprintf (file
, "%d\n", nb_writes
);
1156 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
1157 if (PDR_TYPE (pdr
) != PDR_READ
)
1158 print_pdr (file
, pdr
, verbosity
);
1161 fprintf (file
, "#)\n");
1164 fprintf (file
, "#)\n");
1167 /* Print to STDERR all the data references of PBB. */
1170 debug_pdrs (poly_bb_p pbb
, int verbosity
)
1172 print_pdrs (stderr
, pbb
, verbosity
);
1175 /* Print to FILE the body of PBB, at some VERBOSITY level.
1176 If statement_body_provided is false statement body is not printed. */
1179 print_pbb_body (FILE *file
, poly_bb_p pbb
, int verbosity
,
1180 bool statement_body_provided
)
1183 fprintf (file
, "# Body (\n");
1185 if (!statement_body_provided
)
1188 fprintf (file
, "# Statement body is not provided\n");
1190 fprintf (file
, "0\n");
1195 fprintf (file
, "# Statement body is provided\n");
1196 fprintf (file
, "1\n");
1199 fprintf (file
, "# Original iterator names\n# Iterator names are not provided yet.\n");
1202 fprintf (file
, "# Statement body\n");
1204 fprintf (file
, "{\n");
1205 dump_bb (pbb_bb (pbb
), file
, 0);
1206 fprintf (file
, "}\n");
1209 fprintf (file
, "#)\n");
1212 /* Print to FILE the domain and scattering function of PBB, at some
1216 print_pbb (FILE *file
, poly_bb_p pbb
, int verbosity
)
1220 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1221 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
1222 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
1225 openscop_print_pbb_domain (file
, pbb
, verbosity
);
1226 print_scattering_function (file
, pbb
, verbosity
);
1227 print_pdrs (file
, pbb
, verbosity
);
1228 print_pbb_body (file
, pbb
, verbosity
, false);
1231 fprintf (file
, "#)\n");
1234 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
1237 print_scop_params (FILE *file
, scop_p scop
, int verbosity
)
1243 fprintf (file
, "# parameters (\n");
1245 if (VEC_length (tree
, SESE_PARAMS (SCOP_REGION (scop
))))
1248 fprintf (file
, "# Parameter names are provided\n");
1250 fprintf (file
, "1\n");
1253 fprintf (file
, "# Parameter names\n");
1258 fprintf (file
, "# Parameter names are not provided\n");
1259 fprintf (file
, "0\n");
1262 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (SCOP_REGION (scop
)), i
, t
); i
++)
1264 print_generic_expr (file
, t
, 0);
1265 fprintf (file
, " ");
1268 fprintf (file
, "\n");
1271 fprintf (file
, "#)\n");
1274 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1278 openscop_print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
1284 fprintf (file
, "# Context (\n");
1285 fprintf (file
, "#eq");
1287 for (i
= 0; i
< scop_nb_params (scop
); i
++)
1288 fprintf (file
, " p%d", (int) i
);
1290 fprintf (file
, " cst\n");
1293 if (SCOP_CONTEXT (scop
))
1294 openscop_print_powerset_matrix (file
, SCOP_CONTEXT (scop
), 0, 0, 0,
1295 scop_nb_params (scop
));
1297 fprintf (file
, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop
) + 2,
1298 (int) scop_nb_params (scop
));
1301 fprintf (file
, "# )\n");
1304 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
1307 print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
1313 fprintf (file
, "# Context (\n");
1314 fprintf (file
, "#eq");
1316 for (i
= 0; i
< scop_nb_params (scop
); i
++)
1317 fprintf (file
, " p%d", (int) i
);
1319 fprintf (file
, " cst\n");
1322 if (SCOP_CONTEXT (scop
))
1323 ppl_print_powerset_matrix (file
, SCOP_CONTEXT (scop
));
1325 fprintf (file
, "0 %d\n", (int) scop_nb_params (scop
) + 2);
1328 fprintf (file
, "# )\n");
1331 /* Print to FILE the SCOP header: context, parameters, and statements
1335 print_scop_header (FILE *file
, scop_p scop
, int verbosity
)
1337 fprintf (file
, "SCoP 1\n#(\n");
1338 fprintf (file
, "# Language\nGimple\n");
1339 openscop_print_scop_context (file
, scop
, verbosity
);
1340 print_scop_params (file
, scop
, verbosity
);
1343 fprintf (file
, "# Number of statements\n");
1345 fprintf (file
, "%d\n",VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1348 /* Print to FILE the SCOP, at some VERBOSITY level. */
1351 print_scop (FILE *file
, scop_p scop
, int verbosity
)
1356 print_scop_header (file
, scop
, verbosity
);
1358 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1359 print_pbb (file
, pbb
, verbosity
);
1363 fprintf (file
, "# original_lst (\n");
1364 print_lst (file
, SCOP_ORIGINAL_SCHEDULE (scop
), 0);
1365 fprintf (file
, "\n#)\n");
1367 fprintf (file
, "# transformed_lst (\n");
1368 print_lst (file
, SCOP_TRANSFORMED_SCHEDULE (scop
), 0);
1369 fprintf (file
, "\n#)\n");
1372 fprintf (file
, "#)\n");
1375 /* Print to FILE the input file that CLooG would expect as input, at
1376 some VERBOSITY level. */
1379 print_cloog (FILE *file
, scop_p scop
, int verbosity
)
1384 fprintf (file
, "# SCoP (generated by GCC/Graphite\n");
1386 fprintf (file
, "# CLooG output language\n");
1387 fprintf (file
, "c\n");
1389 print_scop_context (file
, scop
, verbosity
);
1390 print_scop_params (file
, scop
, verbosity
);
1393 fprintf (file
, "# Number of statements\n");
1395 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1397 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1400 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1402 print_pbb_domain (file
, pbb
, verbosity
);
1403 fprintf (file
, "0 0 0");
1406 fprintf (file
, "# For future CLooG options.\n");
1408 fprintf (file
, "\n");
1411 fprintf (file
, "#)\n");
1414 fprintf (file
, "0");
1416 fprintf (file
, "# Don't set the iterator names.\n");
1418 fprintf (file
, "\n");
1421 fprintf (file
, "# Number of scattering functions\n");
1423 fprintf (file
, "%d\n", VEC_length (poly_bb_p
, SCOP_BBS (scop
)));
1424 unify_scattering_dimensions (scop
);
1426 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1428 if (!PBB_TRANSFORMED (pbb
)
1429 || !(PBB_TRANSFORMED_SCATTERING (pbb
)
1430 || PBB_ORIGINAL_SCATTERING (pbb
)))
1434 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
1436 print_scattering_function_1 (file
, pbb
, verbosity
);
1439 fprintf (file
, "#)\n");
1442 fprintf (file
, "0");
1444 fprintf (file
, "# Don't set the scattering dimension names.\n");
1446 fprintf (file
, "\n");
1448 fprintf (file
, "#)\n");
1451 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
1454 debug_pbb_domain (poly_bb_p pbb
, int verbosity
)
1456 print_pbb_domain (stderr
, pbb
, verbosity
);
1459 /* Print to FILE the domain and scattering function of PBB, at some
1463 debug_pbb (poly_bb_p pbb
, int verbosity
)
1465 print_pbb (stderr
, pbb
, verbosity
);
1468 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
1471 debug_scop_context (scop_p scop
, int verbosity
)
1473 print_scop_context (stderr
, scop
, verbosity
);
1476 /* Print to STDERR the SCOP, at some VERBOSITY level. */
1479 debug_scop (scop_p scop
, int verbosity
)
1481 print_scop (stderr
, scop
, verbosity
);
1484 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1488 debug_cloog (scop_p scop
, int verbosity
)
1490 print_cloog (stderr
, scop
, verbosity
);
1493 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1497 debug_scop_params (scop_p scop
, int verbosity
)
1499 print_scop_params (stderr
, scop
, verbosity
);
1503 /* The dimension in the transformed scattering polyhedron of PBB
1504 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
1507 psct_scattering_dim_for_loop_depth (poly_bb_p pbb
, graphite_dim_t loop_depth
)
1509 ppl_const_Constraint_System_t pcs
;
1510 ppl_Constraint_System_const_iterator_t cit
, cend
;
1511 ppl_const_Constraint_t cstr
;
1512 ppl_Polyhedron_t ph
= PBB_TRANSFORMED_SCATTERING (pbb
);
1513 ppl_dimension_type iter
= psct_iterator_dim (pbb
, loop_depth
);
1514 ppl_Linear_Expression_t expr
;
1515 ppl_Coefficient_t coef
;
1520 ppl_new_Coefficient (&coef
);
1521 ppl_Polyhedron_get_constraints (ph
, &pcs
);
1522 ppl_new_Constraint_System_const_iterator (&cit
);
1523 ppl_new_Constraint_System_const_iterator (&cend
);
1525 for (ppl_Constraint_System_begin (pcs
, cit
),
1526 ppl_Constraint_System_end (pcs
, cend
);
1527 !ppl_Constraint_System_const_iterator_equal_test (cit
, cend
);
1528 ppl_Constraint_System_const_iterator_increment (cit
))
1530 ppl_Constraint_System_const_iterator_dereference (cit
, &cstr
);
1531 ppl_new_Linear_Expression_from_Constraint (&expr
, cstr
);
1532 ppl_Linear_Expression_coefficient (expr
, iter
, coef
);
1533 ppl_Coefficient_to_mpz_t (coef
, val
);
1535 if (mpz_sgn (val
) == 0)
1537 ppl_delete_Linear_Expression (expr
);
1541 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
1543 ppl_dimension_type scatter
= psct_scattering_dim (pbb
, i
);
1545 ppl_Linear_Expression_coefficient (expr
, scatter
, coef
);
1546 ppl_Coefficient_to_mpz_t (coef
, val
);
1548 if (mpz_sgn (val
) != 0)
1551 ppl_delete_Linear_Expression (expr
);
1552 ppl_delete_Coefficient (coef
);
1553 ppl_delete_Constraint_System_const_iterator (cit
);
1554 ppl_delete_Constraint_System_const_iterator (cend
);
1564 /* Returns the number of iterations NITER of the loop around PBB at
1565 depth LOOP_DEPTH. */
1568 pbb_number_of_iterations (poly_bb_p pbb
,
1569 graphite_dim_t loop_depth
,
1572 ppl_Linear_Expression_t le
;
1573 ppl_dimension_type dim
;
1575 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
), &dim
);
1576 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
1577 ppl_set_coef (le
, pbb_iterator_dim (pbb
, loop_depth
), 1);
1578 mpz_set_si (niter
, -1);
1579 ppl_max_for_le_pointset (PBB_DOMAIN (pbb
), le
, niter
);
1580 ppl_delete_Linear_Expression (le
);
1583 /* Returns the number of iterations NITER of the loop around PBB at
1584 time(scattering) dimension TIME_DEPTH. */
1587 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
1588 graphite_dim_t time_depth
,
1591 ppl_Pointset_Powerset_C_Polyhedron_t ext_domain
, sctr
;
1592 ppl_Linear_Expression_t le
;
1593 ppl_dimension_type dim
;
1595 /* Takes together domain and scattering polyhedrons, and composes
1596 them into the bigger polyhedron that has the following format:
1598 t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}
1601 | t0..t_{n-1} are time dimensions (scattering dimensions)
1602 | l0..l_{nclc-1} are local variables in scattering function
1603 | i0..i_{niter-1} are original iteration variables
1604 | g0..g_{nparam-1} are global parameters. */
1606 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr
,
1607 PBB_TRANSFORMED_SCATTERING (pbb
));
1609 /* Extend the iteration domain with the scattering dimensions:
1610 0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}. */
1611 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1612 (&ext_domain
, PBB_DOMAIN (pbb
));
1613 ppl_insert_dimensions_pointset (ext_domain
, 0,
1614 pbb_nb_scattering_transform (pbb
)
1615 + pbb_nb_local_vars (pbb
));
1617 /* Add to sctr the extended domain. */
1618 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr
, ext_domain
);
1620 /* Extract the number of iterations. */
1621 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr
, &dim
);
1622 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
1623 ppl_set_coef (le
, time_depth
, 1);
1624 mpz_set_si (niter
, -1);
1625 ppl_max_for_le_pointset (sctr
, le
, niter
);
1627 ppl_delete_Linear_Expression (le
);
1628 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr
);
1629 ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain
);
1632 /* Translates LOOP to LST. */
1635 loop_to_lst (loop_p loop
, VEC (poly_bb_p
, heap
) *bbs
, int *i
)
1638 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1640 for (; VEC_iterate (poly_bb_p
, bbs
, *i
, pbb
); (*i
)++)
1643 basic_block bb
= GBB_BB (PBB_BLACK_BOX (pbb
));
1645 if (bb
->loop_father
== loop
)
1646 stmt
= new_lst_stmt (pbb
);
1647 else if (flow_bb_inside_loop_p (loop
, bb
))
1649 loop_p next
= loop
->inner
;
1651 while (next
&& !flow_bb_inside_loop_p (next
, bb
))
1654 stmt
= loop_to_lst (next
, bbs
, i
);
1659 return new_lst_loop (seq
);
1662 VEC_safe_push (lst_p
, heap
, seq
, stmt
);
1665 return new_lst_loop (seq
);
1668 /* Reads the original scattering of the SCOP and returns an LST
1672 scop_to_lst (scop_p scop
)
1675 int i
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
1676 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
1677 sese region
= SCOP_REGION (scop
);
1679 for (i
= 0; i
< n
; i
++)
1681 poly_bb_p pbb
= VEC_index (poly_bb_p
, SCOP_BBS (scop
), i
);
1682 loop_p loop
= outermost_loop_in_sese (region
, GBB_BB (PBB_BLACK_BOX (pbb
)));
1684 if (loop_in_sese_p (loop
, region
))
1685 res
= loop_to_lst (loop
, SCOP_BBS (scop
), &i
);
1687 res
= new_lst_stmt (pbb
);
1689 VEC_safe_push (lst_p
, heap
, seq
, res
);
1692 res
= new_lst_loop (seq
);
1693 SCOP_ORIGINAL_SCHEDULE (scop
) = res
;
1694 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (res
);
1697 /* Print to FILE on a new line COLUMN white spaces. */
1700 lst_indent_to (FILE *file
, int column
)
1705 fprintf (file
, "\n#");
1707 for (i
= 0; i
< column
; i
++)
1708 fprintf (file
, " ");
1711 /* Print LST to FILE with INDENT spaces of indentation. */
1714 print_lst (FILE *file
, lst_p lst
, int indent
)
1719 lst_indent_to (file
, indent
);
1721 if (LST_LOOP_P (lst
))
1726 if (LST_LOOP_FATHER (lst
))
1727 fprintf (file
, "%d (loop", lst_dewey_number (lst
));
1729 fprintf (file
, "#(root");
1731 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1732 print_lst (file
, l
, indent
+ 2);
1734 fprintf (file
, ")");
1737 fprintf (file
, "%d stmt_%d", lst_dewey_number (lst
), pbb_index (LST_PBB (lst
)));
1740 /* Print LST to STDERR. */
1743 debug_lst (lst_p lst
)
1745 print_lst (stderr
, lst
, 0);
1748 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1751 dot_lst_1 (FILE *file
, lst_p lst
)
1756 if (LST_LOOP_P (lst
))
1761 if (!LST_LOOP_FATHER (lst
))
1762 fprintf (file
, "L -> L_%d_%d\n",
1764 lst_dewey_number (lst
));
1766 fprintf (file
, "L_%d_%d -> L_%d_%d\n",
1767 lst_depth (LST_LOOP_FATHER (lst
)),
1768 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1770 lst_dewey_number (lst
));
1772 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1773 dot_lst_1 (file
, l
);
1777 fprintf (file
, "L_%d_%d -> S_%d\n",
1778 lst_depth (LST_LOOP_FATHER (lst
)),
1779 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1780 pbb_index (LST_PBB (lst
)));
1784 /* Display the LST using dotty. */
1789 /* When debugging, enable the following code. This cannot be used
1790 in production compilers because it calls "system". */
1792 FILE *stream
= fopen ("/tmp/lst.dot", "w");
1793 gcc_assert (stream
);
1795 fputs ("digraph all {\n", stream
);
1796 dot_lst_1 (stream
, lst
);
1797 fputs ("}\n\n", stream
);
1800 system ("dotty /tmp/lst.dot &");
1802 fputs ("digraph all {\n", stderr
);
1803 dot_lst_1 (stderr
, lst
);
1804 fputs ("}\n\n", stderr
);