1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass converts GIMPLE to GRAPHITE, performs some loop
22 transformations and then converts the resulting representation back
25 An early description of this pass can be found in the GCC Summit'06
26 paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
27 The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
30 One important document to read is CLooG's internal manual:
31 http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
32 that describes the data structure of loops used in this file, and
33 the functions that are used for transforming the code. */
37 #include "coretypes.h"
42 #include "basic-block.h"
43 #include "diagnostic.h"
44 #include "tree-flow.h"
45 #include "tree-dump.h"
48 #include "tree-chrec.h"
49 #include "tree-data-ref.h"
50 #include "tree-scalar-evolution.h"
51 #include "tree-pass.h"
52 #include "value-prof.h"
53 #include "pointer-set.h"
61 #include "cloog/cloog.h"
63 #include "graphite-cloog-compat.h"
64 #include "graphite-ppl.h"
66 #include "graphite-poly.h"
67 #include "graphite-scop-detection.h"
68 #include "graphite-clast-to-gimple.h"
69 #include "graphite-sese-to-poly.h"
71 /* Print global statistics to FILE. */
74 print_global_statistics (FILE* file
)
79 long n_conditions
= 0;
83 long n_p_conditions
= 0;
89 gimple_stmt_iterator psi
;
94 /* Ignore artificial surrounding loop. */
95 if (bb
== bb
->loop_father
->header
99 n_p_loops
+= bb
->count
;
102 if (VEC_length (edge
, bb
->succs
) > 1)
105 n_p_conditions
+= bb
->count
;
108 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
111 n_p_stmts
+= bb
->count
;
115 fprintf (file
, "\nGlobal statistics (");
116 fprintf (file
, "BBS:%ld, ", n_bbs
);
117 fprintf (file
, "LOOPS:%ld, ", n_loops
);
118 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
119 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
120 fprintf (file
, "\nGlobal profiling statistics (");
121 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
122 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
123 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
124 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
127 /* Print statistics for SCOP to FILE. */
130 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
135 long n_conditions
= 0;
139 long n_p_conditions
= 0;
145 gimple_stmt_iterator psi
;
146 loop_p loop
= bb
->loop_father
;
148 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
152 n_p_bbs
+= bb
->count
;
154 if (VEC_length (edge
, bb
->succs
) > 1)
157 n_p_conditions
+= bb
->count
;
160 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
163 n_p_stmts
+= bb
->count
;
166 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
169 n_p_loops
+= bb
->count
;
173 fprintf (file
, "\nSCoP statistics (");
174 fprintf (file
, "BBS:%ld, ", n_bbs
);
175 fprintf (file
, "LOOPS:%ld, ", n_loops
);
176 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
177 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
178 fprintf (file
, "\nSCoP profiling statistics (");
179 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
180 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
181 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
182 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
185 /* Print statistics for SCOPS to FILE. */
188 print_graphite_statistics (FILE* file
, VEC (scop_p
, heap
) *scops
)
194 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
195 print_graphite_scop_statistics (file
, scop
);
198 /* Initialize graphite: when there are no loops returns false. */
201 graphite_initialize (void)
205 if (number_of_loops () <= 1
206 /* FIXME: This limit on the number of basic blocks of a function
207 should be removed when the SCOP detection is faster. */
208 || n_basic_blocks
> PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION
))
210 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
211 print_global_statistics (dump_file
);
217 recompute_all_dominators ();
218 initialize_original_copy_tables ();
220 ppl_initialized
= ppl_initialize ();
221 gcc_assert (ppl_initialized
== 0);
225 if (dump_file
&& dump_flags
)
226 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
231 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
235 graphite_finalize (bool need_cfg_cleanup_p
)
237 if (need_cfg_cleanup_p
)
241 profile_status
= PROFILE_ABSENT
;
242 release_recorded_exits ();
243 tree_estimate_probability ();
248 free_original_copy_tables ();
250 if (dump_file
&& dump_flags
)
251 print_loops (dump_file
, 3);
254 /* Perform a set of linear transforms on the loops of the current
258 graphite_transform_loops (void)
262 bool need_cfg_cleanup_p
= false;
263 VEC (scop_p
, heap
) *scops
= NULL
;
264 htab_t bb_pbb_mapping
;
266 if (!graphite_initialize ())
269 build_scops (&scops
);
271 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 print_graphite_statistics (dump_file
, scops
);
274 print_global_statistics (dump_file
);
277 bb_pbb_mapping
= htab_create (10, bb_pbb_map_hash
, eq_bb_pbb_map
, free
);
279 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
280 if (dbg_cnt (graphite_scop
))
282 build_poly_scop (scop
);
284 if (POLY_SCOP_P (scop
)
285 && apply_poly_transforms (scop
)
286 && gloog (scop
, bb_pbb_mapping
))
287 need_cfg_cleanup_p
= true;
290 htab_delete (bb_pbb_mapping
);
292 graphite_finalize (need_cfg_cleanup_p
);
295 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
298 graphite_transform_loops (void)
300 sorry ("Graphite loop optimizations cannot be used");