1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2013 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. */
40 #include <isl/options.h>
41 #include <isl/union_map.h>
42 #include <cloog/cloog.h>
43 #include <cloog/isl/domain.h>
44 #include <cloog/isl/cloog.h>
48 #include "coretypes.h"
49 #include "diagnostic-core.h"
51 #include "tree-dump.h"
53 #include "tree-chrec.h"
54 #include "tree-data-ref.h"
55 #include "tree-scalar-evolution.h"
58 #include "tree-parloops.h"
59 #include "tree-pass.h"
63 #include "graphite-poly.h"
64 #include "graphite-scop-detection.h"
65 #include "graphite-clast-to-gimple.h"
66 #include "graphite-sese-to-poly.h"
67 #include "graphite-htab.h"
69 CloogState
*cloog_state
;
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 (EDGE_COUNT (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 (EDGE_COUNT (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
> scops
)
194 FOR_EACH_VEC_ELT (scops
, i
, scop
)
195 print_graphite_scop_statistics (file
, scop
);
198 /* Initialize graphite: when there are no loops returns false. */
201 graphite_initialize (isl_ctx
*ctx
)
203 if (number_of_loops (cfun
) <= 1
204 /* FIXME: This limit on the number of basic blocks of a function
205 should be removed when the SCOP detection is faster. */
206 || n_basic_blocks
> PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION
))
208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
209 print_global_statistics (dump_file
);
216 recompute_all_dominators ();
217 initialize_original_copy_tables ();
219 cloog_state
= cloog_isl_state_malloc (ctx
);
221 if (dump_file
&& dump_flags
)
222 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
227 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
231 graphite_finalize (bool need_cfg_cleanup_p
)
233 if (need_cfg_cleanup_p
)
237 profile_status
= PROFILE_ABSENT
;
238 release_recorded_exits ();
239 tree_estimate_probability ();
242 cloog_state_free (cloog_state
);
243 free_original_copy_tables ();
245 if (dump_file
&& dump_flags
)
246 print_loops (dump_file
, 3);
249 isl_ctx
*the_isl_ctx
;
251 /* Perform a set of linear transforms on the loops of the current
255 graphite_transform_loops (void)
259 bool need_cfg_cleanup_p
= false;
260 vec
<scop_p
> scops
= vNULL
;
261 bb_pbb_htab_type bb_pbb_mapping
;
264 /* If a function is parallel it was most probably already run through graphite
265 once. No need to run again. */
266 if (parallelized_function_p (cfun
->decl
))
269 ctx
= isl_ctx_alloc ();
270 isl_options_set_on_error (ctx
, ISL_ON_ERROR_ABORT
);
271 if (!graphite_initialize (ctx
))
275 build_scops (&scops
);
277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
279 print_graphite_statistics (dump_file
, scops
);
280 print_global_statistics (dump_file
);
283 bb_pbb_mapping
.create (10);
285 FOR_EACH_VEC_ELT (scops
, i
, scop
)
286 if (dbg_cnt (graphite_scop
))
289 build_poly_scop (scop
);
291 if (POLY_SCOP_P (scop
)
292 && apply_poly_transforms (scop
)
293 && gloog (scop
, bb_pbb_mapping
))
294 need_cfg_cleanup_p
= true;
297 bb_pbb_mapping
.dispose ();
299 graphite_finalize (need_cfg_cleanup_p
);
304 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
307 graphite_transform_loops (void)
309 sorry ("Graphite loop optimizations cannot be used");
316 graphite_transforms (void)
321 graphite_transform_loops ();
327 gate_graphite_transforms (void)
329 /* Enable -fgraphite pass if any one of the graphite optimization flags
332 || flag_loop_interchange
333 || flag_loop_strip_mine
334 || flag_graphite_identity
335 || flag_loop_parallelize_all
336 || flag_loop_optimize_isl
)
339 return flag_graphite
!= 0;
344 const pass_data pass_data_graphite
=
346 GIMPLE_PASS
, /* type */
347 "graphite0", /* name */
348 OPTGROUP_LOOP
, /* optinfo_flags */
350 false, /* has_execute */
351 TV_GRAPHITE
, /* tv_id */
352 ( PROP_cfg
| PROP_ssa
), /* properties_required */
353 0, /* properties_provided */
354 0, /* properties_destroyed */
355 0, /* todo_flags_start */
356 0, /* todo_flags_finish */
359 class pass_graphite
: public gimple_opt_pass
362 pass_graphite (gcc::context
*ctxt
)
363 : gimple_opt_pass (pass_data_graphite
, ctxt
)
366 /* opt_pass methods: */
367 bool gate () { return gate_graphite_transforms (); }
369 }; // class pass_graphite
374 make_pass_graphite (gcc::context
*ctxt
)
376 return new pass_graphite (ctxt
);
381 const pass_data pass_data_graphite_transforms
=
383 GIMPLE_PASS
, /* type */
384 "graphite", /* name */
385 OPTGROUP_LOOP
, /* optinfo_flags */
387 true, /* has_execute */
388 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
389 ( PROP_cfg
| PROP_ssa
), /* properties_required */
390 0, /* properties_provided */
391 0, /* properties_destroyed */
392 0, /* todo_flags_start */
393 0, /* todo_flags_finish */
396 class pass_graphite_transforms
: public gimple_opt_pass
399 pass_graphite_transforms (gcc::context
*ctxt
)
400 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
403 /* opt_pass methods: */
404 bool gate () { return gate_graphite_transforms (); }
405 unsigned int execute () { return graphite_transforms (); }
407 }; // class pass_graphite_transforms
412 make_pass_graphite_transforms (gcc::context
*ctxt
)
414 return new pass_graphite_transforms (ctxt
);