1 /* Graphite polyhedral representation.
2 Copyright (C) 2009-2015 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/>. */
27 #include <isl/union_map.h>
28 #include <isl/constraint.h>
33 /* Since ISL-0.13, the extern is in val_gmp.h. */
34 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
37 #include <isl/val_gmp.h>
38 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
44 #include "coretypes.h"
45 #include "diagnostic-core.h"
51 #include "fold-const.h"
54 #include "hard-reg-set.h"
57 #include "dominance.h"
59 #include "basic-block.h"
60 #include "tree-ssa-alias.h"
61 #include "internal-fn.h"
62 #include "gimple-expr.h"
65 #include "gimple-iterator.h"
66 #include "tree-ssa-loop.h"
68 #include "gimple-pretty-print.h"
70 #include "tree-chrec.h"
71 #include "tree-data-ref.h"
72 #include "tree-scalar-evolution.h"
76 #include "graphite-poly.h"
78 #define OPENSCOP_MAX_STRING 256
81 /* Print to STDERR the GMP value VAL. */
84 debug_gmp_value (mpz_t val
)
86 gmp_fprintf (stderr
, "%Zd", val
);
89 /* Return the maximal loop depth in SCOP. */
92 scop_max_loop_depth (scop_p scop
)
98 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
100 int nb_loops
= pbb_dim_iter_domain (pbb
);
101 if (max_nb_loops
< nb_loops
)
102 max_nb_loops
= nb_loops
;
108 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
112 print_scattering_function_1 (FILE *file
, poly_bb_p pbb
, int verbosity
)
118 fprintf (file
, "# scattering bb_%d (\n", pbb_index (pbb
));
119 fprintf (file
, "#eq");
121 for (i
= 0; i
< pbb_nb_scattering_transform (pbb
); i
++)
122 fprintf (file
, " s%d", (int) i
);
124 for (i
= 0; i
< pbb_nb_local_vars (pbb
); i
++)
125 fprintf (file
, " lv%d", (int) i
);
127 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
128 fprintf (file
, " i%d", (int) i
);
130 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
131 fprintf (file
, " p%d", (int) i
);
133 fprintf (file
, " cst\n");
136 fprintf (file
, "isl\n");
137 print_isl_map (file
, pbb
->transformed
? pbb
->transformed
: pbb
->schedule
);
140 fprintf (file
, "#)\n");
143 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
147 print_scattering_function (FILE *file
, poly_bb_p pbb
, int verbosity
)
149 if (!PBB_TRANSFORMED (pbb
))
152 if (pbb
->schedule
|| pbb
->transformed
)
155 fprintf (file
, "# Scattering function is provided\n");
157 fprintf (file
, "1\n");
162 fprintf (file
, "# Scattering function is not provided\n");
164 fprintf (file
, "0\n");
168 print_scattering_function_1 (file
, pbb
, verbosity
);
171 fprintf (file
, "# Scattering names are not provided\n");
173 fprintf (file
, "0\n");
177 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
181 print_iteration_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
183 print_pbb_domain (file
, pbb
, verbosity
);
186 /* Prints to FILE the scattering functions of every PBB of SCOP. */
189 print_scattering_functions (FILE *file
, scop_p scop
, int verbosity
)
194 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
195 print_scattering_function (file
, pbb
, verbosity
);
198 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
202 print_iteration_domains (FILE *file
, scop_p scop
, int verbosity
)
207 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
208 print_iteration_domain (file
, pbb
, verbosity
);
211 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
215 debug_scattering_function (poly_bb_p pbb
, int verbosity
)
217 print_scattering_function (stderr
, pbb
, verbosity
);
220 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
224 debug_iteration_domain (poly_bb_p pbb
, int verbosity
)
226 print_iteration_domain (stderr
, pbb
, verbosity
);
229 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
230 some VERBOSITY level. */
233 debug_scattering_functions (scop_p scop
, int verbosity
)
235 print_scattering_functions (stderr
, scop
, verbosity
);
238 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
239 some VERBOSITY level. */
242 debug_iteration_domains (scop_p scop
, int verbosity
)
244 print_iteration_domains (stderr
, scop
, verbosity
);
247 /* Apply graphite transformations to all the basic blocks of SCOP. */
250 apply_poly_transforms (scop_p scop
)
252 bool transform_done
= false;
254 /* Generate code even if we did not apply any real transformation.
255 This also allows to check the performance for the identity
256 transformation: GIMPLE -> GRAPHITE -> GIMPLE
257 Keep in mind that CLooG optimizes in control, so the loop structure
258 may change, even if we only use -fgraphite-identity. */
259 if (flag_graphite_identity
)
260 transform_done
= true;
262 if (flag_loop_parallelize_all
)
263 transform_done
= true;
266 transform_done
|= scop_do_block (scop
);
269 if (flag_loop_strip_mine
)
270 transform_done
|= scop_do_strip_mine (scop
, 0);
272 if (flag_loop_interchange
)
273 transform_done
|= scop_do_interchange (scop
);
276 /* This pass needs to be run at the final stage, as it does not
278 if (flag_loop_optimize_isl
|| flag_loop_unroll_jam
)
279 transform_done
|= optimize_isl (scop
);
281 return transform_done
;
284 /* Create a new polyhedral data reference and add it to PBB. It is
285 defined by its ACCESSES, its TYPE, and the number of subscripts
289 new_poly_dr (poly_bb_p pbb
, int dr_base_object_set
,
290 enum poly_dr_type type
, void *cdr
, graphite_dim_t nb_subscripts
,
291 isl_map
*acc
, isl_set
*extent
)
294 poly_dr_p pdr
= XNEW (struct poly_dr
);
297 PDR_BASE_OBJECT_SET (pdr
) = dr_base_object_set
;
298 PDR_NB_REFS (pdr
) = 1;
301 pdr
->extent
= extent
;
302 PDR_TYPE (pdr
) = type
;
304 PDR_NB_SUBSCRIPTS (pdr
) = nb_subscripts
;
305 PBB_DRS (pbb
).safe_push (pdr
);
308 /* Free polyhedral data reference PDR. */
311 free_poly_dr (poly_dr_p pdr
)
313 isl_map_free (pdr
->accesses
);
314 isl_set_free (pdr
->extent
);
318 /* Create a new polyhedral black box. */
321 new_poly_bb (scop_p scop
, void *black_box
)
323 poly_bb_p pbb
= XNEW (struct poly_bb
);
326 pbb
->schedule
= NULL
;
327 pbb
->transformed
= NULL
;
329 pbb
->map_sepclass
= NULL
;
330 PBB_SCOP (pbb
) = scop
;
331 pbb_set_black_box (pbb
, black_box
);
332 PBB_TRANSFORMED (pbb
) = NULL
;
333 PBB_SAVED (pbb
) = NULL
;
334 PBB_ORIGINAL (pbb
) = NULL
;
335 PBB_DRS (pbb
).create (3);
336 PBB_IS_REDUCTION (pbb
) = false;
337 GBB_PBB ((gimple_bb_p
) black_box
) = pbb
;
342 /* Free polyhedral black box. */
345 free_poly_bb (poly_bb_p pbb
)
350 isl_set_free (pbb
->domain
);
351 isl_map_free (pbb
->schedule
);
352 isl_map_free (pbb
->transformed
);
353 isl_map_free (pbb
->saved
);
355 if (PBB_DRS (pbb
).exists ())
356 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
359 PBB_DRS (pbb
).release ();
364 print_pdr_access_layout (FILE *file
, poly_bb_p pbb
, poly_dr_p pdr
)
368 fprintf (file
, "# eq");
370 fprintf (file
, " alias");
372 for (i
= 0; i
< PDR_NB_SUBSCRIPTS (pdr
); i
++)
373 fprintf (file
, " sub%d", (int) i
);
375 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
376 fprintf (file
, " i%d", (int) i
);
378 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
379 fprintf (file
, " p%d", (int) i
);
381 fprintf (file
, " cst\n");
384 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
388 print_pdr (FILE *file
, poly_dr_p pdr
, int verbosity
)
392 fprintf (file
, "# pdr_%d (", PDR_ID (pdr
));
394 switch (PDR_TYPE (pdr
))
397 fprintf (file
, "read \n");
401 fprintf (file
, "write \n");
405 fprintf (file
, "may_write \n");
412 dump_data_reference (file
, (data_reference_p
) PDR_CDR (pdr
));
417 fprintf (file
, "# data accesses (\n");
418 print_pdr_access_layout (file
, PDR_PBB (pdr
), pdr
);
421 /* XXX isl dump accesses/subscripts */
424 fprintf (file
, "#)\n");
427 fprintf (file
, "#)\n");
430 /* Prints to STDERR the polyhedral data reference PDR, at some
434 debug_pdr (poly_dr_p pdr
, int verbosity
)
436 print_pdr (stderr
, pdr
, verbosity
);
439 /* Creates a new SCOP containing REGION. */
442 new_scop (void *region
)
444 scop_p scop
= XNEW (struct scop
);
446 scop
->context
= NULL
;
447 scop
->must_raw
= NULL
;
448 scop
->may_raw
= NULL
;
449 scop
->must_raw_no_source
= NULL
;
450 scop
->may_raw_no_source
= NULL
;
451 scop
->must_war
= NULL
;
452 scop
->may_war
= NULL
;
453 scop
->must_war_no_source
= NULL
;
454 scop
->may_war_no_source
= NULL
;
455 scop
->must_waw
= NULL
;
456 scop
->may_waw
= NULL
;
457 scop
->must_waw_no_source
= NULL
;
458 scop
->may_waw_no_source
= NULL
;
459 scop_set_region (scop
, region
);
460 SCOP_BBS (scop
).create (3);
461 SCOP_ORIGINAL_SCHEDULE (scop
) = NULL
;
462 SCOP_TRANSFORMED_SCHEDULE (scop
) = NULL
;
463 SCOP_SAVED_SCHEDULE (scop
) = NULL
;
464 POLY_SCOP_P (scop
) = false;
472 free_scop (scop_p scop
)
477 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
480 SCOP_BBS (scop
).release ();
482 isl_set_free (scop
->context
);
483 isl_union_map_free (scop
->must_raw
);
484 isl_union_map_free (scop
->may_raw
);
485 isl_union_map_free (scop
->must_raw_no_source
);
486 isl_union_map_free (scop
->may_raw_no_source
);
487 isl_union_map_free (scop
->must_war
);
488 isl_union_map_free (scop
->may_war
);
489 isl_union_map_free (scop
->must_war_no_source
);
490 isl_union_map_free (scop
->may_war_no_source
);
491 isl_union_map_free (scop
->must_waw
);
492 isl_union_map_free (scop
->may_waw
);
493 isl_union_map_free (scop
->must_waw_no_source
);
494 isl_union_map_free (scop
->may_waw_no_source
);
495 free_lst (SCOP_ORIGINAL_SCHEDULE (scop
));
496 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
497 free_lst (SCOP_SAVED_SCHEDULE (scop
));
501 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
505 openscop_print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
508 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
515 fprintf (file
, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb
)->index
);
516 fprintf (file
, "#eq");
518 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
519 fprintf (file
, " i%d", (int) i
);
521 for (i
= 0; i
< pbb_nb_params (pbb
); i
++)
522 fprintf (file
, " p%d", (int) i
);
524 fprintf (file
, " cst\n");
527 fprintf (file
, "XXX isl\n");
530 fprintf (file
, "#)\n");
533 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
536 print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity ATTRIBUTE_UNUSED
)
538 print_isl_set (file
, pbb
->domain
);
541 /* Dump the cases of a graphite basic block GBB on FILE. */
544 dump_gbb_cases (FILE *file
, gimple_bb_p gbb
)
553 cases
= GBB_CONDITION_CASES (gbb
);
554 if (cases
.is_empty ())
557 fprintf (file
, "# cases bb_%d (\n", GBB_BB (gbb
)->index
);
559 FOR_EACH_VEC_ELT (cases
, i
, stmt
)
561 fprintf (file
, "# ");
562 print_gimple_stmt (file
, stmt
, 0, 0);
565 fprintf (file
, "#)\n");
568 /* Dump conditions of a graphite basic block GBB on FILE. */
571 dump_gbb_conditions (FILE *file
, gimple_bb_p gbb
)
575 vec
<gimple
> conditions
;
580 conditions
= GBB_CONDITIONS (gbb
);
581 if (conditions
.is_empty ())
584 fprintf (file
, "# conditions bb_%d (\n", GBB_BB (gbb
)->index
);
586 FOR_EACH_VEC_ELT (conditions
, i
, stmt
)
588 fprintf (file
, "# ");
589 print_gimple_stmt (file
, stmt
, 0, 0);
592 fprintf (file
, "#)\n");
595 /* Print to FILE all the data references of PBB, at some VERBOSITY
599 print_pdrs (FILE *file
, poly_bb_p pbb
, int verbosity
)
606 if (PBB_DRS (pbb
).length () == 0)
609 fprintf (file
, "# Access informations are not provided\n");\
610 fprintf (file
, "0\n");
615 fprintf (file
, "# Data references (\n");
618 fprintf (file
, "# Access informations are provided\n");
619 fprintf (file
, "1\n");
621 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
622 if (PDR_TYPE (pdr
) == PDR_READ
)
628 fprintf (file
, "# Read data references (\n");
631 fprintf (file
, "# Read access informations\n");
632 fprintf (file
, "%d\n", nb_reads
);
634 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
635 if (PDR_TYPE (pdr
) == PDR_READ
)
636 print_pdr (file
, pdr
, verbosity
);
639 fprintf (file
, "#)\n");
642 fprintf (file
, "# Write data references (\n");
645 fprintf (file
, "# Write access informations\n");
646 fprintf (file
, "%d\n", nb_writes
);
648 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
649 if (PDR_TYPE (pdr
) != PDR_READ
)
650 print_pdr (file
, pdr
, verbosity
);
653 fprintf (file
, "#)\n");
656 fprintf (file
, "#)\n");
659 /* Print to STDERR all the data references of PBB. */
662 debug_pdrs (poly_bb_p pbb
, int verbosity
)
664 print_pdrs (stderr
, pbb
, verbosity
);
667 /* Print to FILE the body of PBB, at some VERBOSITY level.
668 If statement_body_provided is false statement body is not printed. */
671 print_pbb_body (FILE *file
, poly_bb_p pbb
, int verbosity
,
672 bool statement_body_provided
)
675 fprintf (file
, "# Body (\n");
677 if (!statement_body_provided
)
680 fprintf (file
, "# Statement body is not provided\n");
682 fprintf (file
, "0\n");
685 fprintf (file
, "#)\n");
690 fprintf (file
, "# Statement body is provided\n");
691 fprintf (file
, "1\n");
694 fprintf (file
, "# Original iterator names\n# Iterator names are not provided yet.\n");
697 fprintf (file
, "# Statement body\n");
699 fprintf (file
, "{\n");
700 dump_bb (file
, pbb_bb (pbb
), 0, 0);
701 fprintf (file
, "}\n");
704 fprintf (file
, "#)\n");
707 /* Print to FILE the domain and scattering function of PBB, at some
711 print_pbb (FILE *file
, poly_bb_p pbb
, int verbosity
)
715 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
716 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
717 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
720 openscop_print_pbb_domain (file
, pbb
, verbosity
);
721 print_scattering_function (file
, pbb
, verbosity
);
722 print_pdrs (file
, pbb
, verbosity
);
723 print_pbb_body (file
, pbb
, verbosity
, false);
726 fprintf (file
, "#)\n");
729 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
732 print_scop_params (FILE *file
, scop_p scop
, int verbosity
)
738 fprintf (file
, "# parameters (\n");
740 if (SESE_PARAMS (SCOP_REGION (scop
)).length ())
743 fprintf (file
, "# Parameter names are provided\n");
745 fprintf (file
, "1\n");
748 fprintf (file
, "# Parameter names\n");
753 fprintf (file
, "# Parameter names are not provided\n");
754 fprintf (file
, "0\n");
757 FOR_EACH_VEC_ELT (SESE_PARAMS (SCOP_REGION (scop
)), i
, t
)
759 print_generic_expr (file
, t
, 0);
763 fprintf (file
, "\n");
766 fprintf (file
, "#)\n");
769 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
773 openscop_print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
779 fprintf (file
, "# Context (\n");
780 fprintf (file
, "#eq");
782 for (i
= 0; i
< scop_nb_params (scop
); i
++)
783 fprintf (file
, " p%d", (int) i
);
785 fprintf (file
, " cst\n");
789 /* XXX isl print context */
790 fprintf (file
, "XXX isl\n");
792 fprintf (file
, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop
) + 2,
793 (int) scop_nb_params (scop
));
796 fprintf (file
, "# )\n");
799 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
802 print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
808 fprintf (file
, "# Context (\n");
809 fprintf (file
, "#eq");
811 for (i
= 0; i
< scop_nb_params (scop
); i
++)
812 fprintf (file
, " p%d", (int) i
);
814 fprintf (file
, " cst\n");
818 print_isl_set (file
, scop
->context
);
820 fprintf (file
, "no isl context %d\n", (int) scop_nb_params (scop
) + 2);
823 fprintf (file
, "# )\n");
826 /* Print to FILE the SCOP, at some VERBOSITY level. */
829 print_scop (FILE *file
, scop_p scop
, int verbosity
)
834 fprintf (file
, "SCoP 1\n#(\n");
835 fprintf (file
, "# Language\nGimple\n");
836 openscop_print_scop_context (file
, scop
, verbosity
);
837 print_scop_params (file
, scop
, verbosity
);
840 fprintf (file
, "# Number of statements\n");
842 fprintf (file
, "%d\n", SCOP_BBS (scop
).length ());
844 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
845 print_pbb (file
, pbb
, verbosity
);
849 fprintf (file
, "# original_lst (\n");
850 print_lst (file
, SCOP_ORIGINAL_SCHEDULE (scop
), 0);
851 fprintf (file
, "\n#)\n");
853 fprintf (file
, "# transformed_lst (\n");
854 print_lst (file
, SCOP_TRANSFORMED_SCHEDULE (scop
), 0);
855 fprintf (file
, "\n#)\n");
858 fprintf (file
, "#)\n");
861 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
864 debug_pbb_domain (poly_bb_p pbb
, int verbosity
)
866 print_pbb_domain (stderr
, pbb
, verbosity
);
869 /* Print to FILE the domain and scattering function of PBB, at some
873 debug_pbb (poly_bb_p pbb
, int verbosity
)
875 print_pbb (stderr
, pbb
, verbosity
);
878 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
881 debug_scop_context (scop_p scop
, int verbosity
)
883 print_scop_context (stderr
, scop
, verbosity
);
886 /* Print to STDERR the SCOP, at some VERBOSITY level. */
889 debug_scop (scop_p scop
, int verbosity
)
891 print_scop (stderr
, scop
, verbosity
);
894 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
898 debug_scop_params (scop_p scop
, int verbosity
)
900 print_scop_params (stderr
, scop
, verbosity
);
903 extern isl_ctx
*the_isl_ctx
;
905 print_isl_set (FILE *f
, isl_set
*set
)
907 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
908 p
= isl_printer_print_set (p
, set
);
909 isl_printer_free (p
);
913 debug_isl_set (isl_set
*set
)
915 print_isl_set (stderr
, set
);
919 print_isl_map (FILE *f
, isl_map
*map
)
921 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
922 p
= isl_printer_print_map (p
, map
);
923 isl_printer_free (p
);
927 debug_isl_map (isl_map
*map
)
929 print_isl_map (stderr
, map
);
933 print_isl_aff (FILE *f
, isl_aff
*aff
)
935 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
936 p
= isl_printer_print_aff (p
, aff
);
937 isl_printer_free (p
);
941 debug_isl_aff (isl_aff
*aff
)
943 print_isl_aff (stderr
, aff
);
947 print_isl_constraint (FILE *f
, isl_constraint
*c
)
949 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
950 p
= isl_printer_print_constraint (p
, c
);
951 isl_printer_free (p
);
955 debug_isl_constraint (isl_constraint
*c
)
957 print_isl_constraint (stderr
, c
);
960 /* Returns the number of iterations RES of the loop around PBB at
961 time(scattering) dimension TIME_DEPTH. */
964 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
965 graphite_dim_t time_depth
,
968 isl_set
*transdomain
;
971 isl_val
*isllb
, *islub
;
973 /* Map the iteration domain through the current scatter, and work
974 on the resulting set. */
975 transdomain
= isl_set_apply (isl_set_copy (pbb
->domain
),
976 isl_map_copy (pbb
->transformed
));
978 /* Select the time_depth' dimension via an affine expression. */
979 dc
= isl_set_get_space (transdomain
);
980 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
981 aff
= isl_aff_set_coefficient_si (aff
, isl_dim_in
, time_depth
, 1);
983 /* And find the min/max for that function. */
984 /* XXX isl check results? */
985 isllb
= isl_set_min_val (transdomain
, aff
);
986 islub
= isl_set_max_val (transdomain
, aff
);
988 islub
= isl_val_sub (islub
, isllb
);
989 islub
= isl_val_add_ui (islub
, 1);
990 isl_val_get_num_gmp (islub
, res
);
992 isl_val_free (islub
);
994 isl_set_free (transdomain
);
997 /* Translates LOOP to LST. */
1000 loop_to_lst (loop_p loop
, vec
<poly_bb_p
> bbs
, int *i
)
1006 for (; bbs
.iterate (*i
, &pbb
); (*i
)++)
1009 basic_block bb
= GBB_BB (PBB_BLACK_BOX (pbb
));
1011 if (bb
->loop_father
== loop
)
1012 stmt
= new_lst_stmt (pbb
);
1013 else if (flow_bb_inside_loop_p (loop
, bb
))
1015 loop_p next
= loop
->inner
;
1017 while (next
&& !flow_bb_inside_loop_p (next
, bb
))
1020 stmt
= loop_to_lst (next
, bbs
, i
);
1025 return new_lst_loop (seq
);
1028 seq
.safe_push (stmt
);
1031 return new_lst_loop (seq
);
1034 /* Reads the original scattering of the SCOP and returns an LST
1038 scop_to_lst (scop_p scop
)
1041 int i
, n
= SCOP_BBS (scop
).length ();
1044 sese region
= SCOP_REGION (scop
);
1046 for (i
= 0; i
< n
; i
++)
1048 poly_bb_p pbb
= SCOP_BBS (scop
)[i
];
1049 loop_p loop
= outermost_loop_in_sese (region
, GBB_BB (PBB_BLACK_BOX (pbb
)));
1051 if (loop_in_sese_p (loop
, region
))
1052 res
= loop_to_lst (loop
, SCOP_BBS (scop
), &i
);
1054 res
= new_lst_stmt (pbb
);
1056 seq
.safe_push (res
);
1059 res
= new_lst_loop (seq
);
1060 SCOP_ORIGINAL_SCHEDULE (scop
) = res
;
1061 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (res
);
1064 /* Print to FILE on a new line COLUMN white spaces. */
1067 lst_indent_to (FILE *file
, int column
)
1072 fprintf (file
, "\n#");
1074 for (i
= 0; i
< column
; i
++)
1075 fprintf (file
, " ");
1078 /* Print LST to FILE with INDENT spaces of indentation. */
1081 print_lst (FILE *file
, lst_p lst
, int indent
)
1086 lst_indent_to (file
, indent
);
1088 if (LST_LOOP_P (lst
))
1093 if (LST_LOOP_FATHER (lst
))
1094 fprintf (file
, "%d (loop", lst_dewey_number (lst
));
1096 fprintf (file
, "#(root");
1098 FOR_EACH_VEC_ELT (LST_SEQ (lst
), i
, l
)
1099 print_lst (file
, l
, indent
+ 2);
1101 fprintf (file
, ")");
1104 fprintf (file
, "%d stmt_%d", lst_dewey_number (lst
), pbb_index (LST_PBB (lst
)));
1107 /* Print LST to STDERR. */
1110 debug_lst (lst_p lst
)
1112 print_lst (stderr
, lst
, 0);
1115 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1118 dot_lst_1 (FILE *file
, lst_p lst
)
1123 if (LST_LOOP_P (lst
))
1128 if (!LST_LOOP_FATHER (lst
))
1129 fprintf (file
, "L -> L_%d_%d\n",
1131 lst_dewey_number (lst
));
1133 fprintf (file
, "L_%d_%d -> L_%d_%d\n",
1134 lst_depth (LST_LOOP_FATHER (lst
)),
1135 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1137 lst_dewey_number (lst
));
1139 FOR_EACH_VEC_ELT (LST_SEQ (lst
), i
, l
)
1140 dot_lst_1 (file
, l
);
1144 fprintf (file
, "L_%d_%d -> S_%d\n",
1145 lst_depth (LST_LOOP_FATHER (lst
)),
1146 lst_dewey_number (LST_LOOP_FATHER (lst
)),
1147 pbb_index (LST_PBB (lst
)));
1151 /* Display the LST using dotty. */
1156 /* When debugging, enable the following code. This cannot be used
1157 in production compilers because it calls "system". */
1159 FILE *stream
= fopen ("/tmp/lst.dot", "w");
1160 gcc_assert (stream
);
1162 fputs ("digraph all {\n", stream
);
1163 dot_lst_1 (stream
, lst
);
1164 fputs ("}\n\n", stream
);
1167 system ("dotty /tmp/lst.dot &");
1169 fputs ("digraph all {\n", stderr
);
1170 dot_lst_1 (stderr
, lst
);
1171 fputs ("}\n\n", stderr
);
1176 /* Reverse the loop around PBB at level DEPTH. */
1179 reverse_loop_at_level (poly_bb_p pbb
, int depth
)
1181 unsigned i
, depth_dim
= psct_dynamic_dim (pbb
, depth
);
1182 isl_space
*d
= isl_map_get_space (pbb
->transformed
);
1183 isl_space
*d1
= isl_space_range (d
);
1184 unsigned n
= isl_space_dim (d1
, isl_dim_out
);
1185 isl_space
*d2
= isl_space_add_dims (d1
, isl_dim_in
, n
);
1186 isl_map
*x
= isl_map_universe (isl_space_copy (d2
));
1187 isl_constraint
*c
= isl_equality_alloc (isl_local_space_from_space (d2
));
1189 for (i
= 0; i
< n
; i
++)
1191 x
= isl_map_equate (x
, isl_dim_in
, i
, isl_dim_out
, i
);
1193 c
= isl_constraint_set_coefficient_si (c
, isl_dim_in
, depth_dim
, 1);
1194 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, depth_dim
, 1);
1195 x
= isl_map_add_constraint (x
, c
);
1199 /* Reverse the loop at level DEPTH for all the PBBS. */
1202 reverse_loop_for_pbbs (scop_p scop
, vec
<poly_bb_p
> pbbs
, int depth
)
1206 isl_space
*space
= isl_space_from_domain (isl_set_get_space (scop
->context
));
1207 isl_union_map
*res
= isl_union_map_empty (space
);
1209 for (i
= 0; pbbs
.iterate (i
, &pbb
); i
++)
1210 res
= isl_union_map_add_map (res
, reverse_loop_at_level (pbb
, depth
));