1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2015 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
33 /* Workaround for GMP 5.1.3 bug, see PR56019. */
36 #include <isl/constraint.h>
39 #include <isl/options.h>
40 #include <isl/union_map.h>
44 #include "coretypes.h"
46 #include "diagnostic-core.h"
48 #include "tree-pass.h"
50 #include "pretty-print.h"
56 #include "fold-const.h"
57 #include "gimple-iterator.h"
59 #include "tree-ssa-loop.h"
60 #include "tree-data-ref.h"
61 #include "tree-scalar-evolution.h"
62 #include "graphite-poly.h"
64 #include "tree-parloops.h"
65 #include "tree-cfgcleanup.h"
66 #include "graphite-scop-detection.h"
67 #include "graphite-isl-ast-to-gimple.h"
68 #include "graphite-sese-to-poly.h"
70 /* Print global statistics to FILE. */
73 print_global_statistics (FILE* file
)
78 long n_conditions
= 0;
82 long n_p_conditions
= 0;
86 FOR_ALL_BB_FN (bb
, cfun
)
88 gimple_stmt_iterator psi
;
93 /* Ignore artificial surrounding loop. */
94 if (bb
== bb
->loop_father
->header
98 n_p_loops
+= bb
->count
;
101 if (EDGE_COUNT (bb
->succs
) > 1)
104 n_p_conditions
+= bb
->count
;
107 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
110 n_p_stmts
+= bb
->count
;
114 fprintf (file
, "\nGlobal statistics (");
115 fprintf (file
, "BBS:%ld, ", n_bbs
);
116 fprintf (file
, "LOOPS:%ld, ", n_loops
);
117 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
118 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
119 fprintf (file
, "\nGlobal profiling statistics (");
120 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
121 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
122 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
123 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
126 /* Print statistics for SCOP to FILE. */
129 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
134 long n_conditions
= 0;
138 long n_p_conditions
= 0;
142 FOR_ALL_BB_FN (bb
, cfun
)
144 gimple_stmt_iterator psi
;
145 loop_p loop
= bb
->loop_father
;
147 if (!bb_in_sese_p (bb
, scop
->region
->region
))
151 n_p_bbs
+= bb
->count
;
153 if (EDGE_COUNT (bb
->succs
) > 1)
156 n_p_conditions
+= bb
->count
;
159 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
162 n_p_stmts
+= bb
->count
;
165 if (loop
->header
== bb
&& loop_in_sese_p (loop
, scop
->region
->region
))
168 n_p_loops
+= bb
->count
;
172 fprintf (file
, "\nFunction Name: %s\n", current_function_name ());
174 edge scop_begin
= scop
->region
->region
.entry
;
175 edge scop_end
= scop
->region
->region
.exit
;
177 fprintf (file
, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
178 scop_begin
->src
->index
, scop_begin
->dest
->index
);
179 fprintf (file
, "exit_edge (bb_%d, bb_%d))",
180 scop_end
->src
->index
, scop_end
->dest
->index
);
182 fprintf (file
, "\nSCoP statistics (");
183 fprintf (file
, "BBS:%ld, ", n_bbs
);
184 fprintf (file
, "LOOPS:%ld, ", n_loops
);
185 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
186 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
187 fprintf (file
, "\nSCoP profiling statistics (");
188 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
189 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
190 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
191 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
194 /* Print statistics for SCOPS to FILE. */
197 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
203 FOR_EACH_VEC_ELT (scops
, i
, scop
)
204 print_graphite_scop_statistics (file
, scop
);
206 /* Print the loop structure. */
207 print_loops (file
, 2);
208 print_loops (file
, 3);
211 /* Initialize graphite: when there are no loops returns false. */
214 graphite_initialize (isl_ctx
*ctx
)
216 int min_loops
= PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION
);
217 int max_bbs
= PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION
);
218 int nbbs
= n_basic_blocks_for_fn (cfun
);
219 int nloops
= number_of_loops (cfun
);
221 if (nloops
<= min_loops
222 /* FIXME: This limit on the number of basic blocks of a function
223 should be removed when the SCOP detection is faster. */
226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
228 if (nloops
<= min_loops
)
229 fprintf (dump_file
, "\nFunction does not have enough loops: "
230 "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n",
233 else if (nbbs
> max_bbs
)
234 fprintf (dump_file
, "\nFunction has too many basic blocks: "
235 "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs
);
237 fprintf (dump_file
, "\nnumber of SCoPs: 0\n");
238 print_global_statistics (dump_file
);
246 recompute_all_dominators ();
247 initialize_original_copy_tables ();
249 if (dump_file
&& dump_flags
)
251 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
252 print_loops (dump_file
, 3);
258 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
262 graphite_finalize (bool need_cfg_cleanup_p
)
264 free_dominance_info (CDI_POST_DOMINATORS
);
265 if (need_cfg_cleanup_p
)
267 free_dominance_info (CDI_DOMINATORS
);
270 profile_status_for_fn (cfun
) = PROFILE_ABSENT
;
271 release_recorded_exits ();
272 tree_estimate_probability ();
275 free_original_copy_tables ();
277 if (dump_file
&& dump_flags
)
278 print_loops (dump_file
, 3);
281 /* Deletes all scops in SCOPS. */
284 free_scops (vec
<scop_p
> scops
)
289 FOR_EACH_VEC_ELT (scops
, i
, scop
)
295 isl_ctx
*the_isl_ctx
;
297 /* Perform a set of linear transforms on the loops of the current
301 graphite_transform_loops (void)
305 bool need_cfg_cleanup_p
= false;
306 vec
<scop_p
> scops
= vNULL
;
309 /* If a function is parallel it was most probably already run through graphite
310 once. No need to run again. */
311 if (parallelized_function_p (cfun
->decl
))
314 ctx
= isl_ctx_alloc ();
315 isl_options_set_on_error (ctx
, ISL_ON_ERROR_ABORT
);
316 if (!graphite_initialize (ctx
))
320 build_scops (&scops
);
322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
324 print_graphite_statistics (dump_file
, scops
);
325 print_global_statistics (dump_file
);
328 FOR_EACH_VEC_ELT (scops
, i
, scop
)
329 if (dbg_cnt (graphite_scop
))
331 scop
->isl_context
= ctx
;
332 build_poly_scop (scop
);
334 if (dump_file
&& dump_flags
)
335 print_scop (dump_file
, scop
, 3);
337 if (POLY_SCOP_P (scop
)
338 && apply_poly_transforms (scop
)
339 && graphite_regenerate_ast_isl (scop
))
340 need_cfg_cleanup_p
= true;
345 graphite_finalize (need_cfg_cleanup_p
);
350 #else /* If ISL is not available: #ifndef HAVE_isl. */
353 graphite_transform_loops (void)
355 sorry ("Graphite loop optimizations cannot be used (ISL is not available).");
362 graphite_transforms (struct function
*fun
)
364 if (number_of_loops (fun
) <= 1)
367 graphite_transform_loops ();
373 gate_graphite_transforms (void)
375 /* Enable -fgraphite pass if any one of the graphite optimization flags
377 if (flag_graphite_identity
378 || flag_loop_parallelize_all
379 || flag_loop_optimize_isl
)
382 return flag_graphite
!= 0;
387 const pass_data pass_data_graphite
=
389 GIMPLE_PASS
, /* type */
390 "graphite0", /* name */
391 OPTGROUP_LOOP
, /* optinfo_flags */
392 TV_GRAPHITE
, /* tv_id */
393 ( PROP_cfg
| PROP_ssa
), /* properties_required */
394 0, /* properties_provided */
395 0, /* properties_destroyed */
396 0, /* todo_flags_start */
397 0, /* todo_flags_finish */
400 class pass_graphite
: public gimple_opt_pass
403 pass_graphite (gcc::context
*ctxt
)
404 : gimple_opt_pass (pass_data_graphite
, ctxt
)
407 /* opt_pass methods: */
408 virtual bool gate (function
*) { return gate_graphite_transforms (); }
410 }; // class pass_graphite
415 make_pass_graphite (gcc::context
*ctxt
)
417 return new pass_graphite (ctxt
);
422 const pass_data pass_data_graphite_transforms
=
424 GIMPLE_PASS
, /* type */
425 "graphite", /* name */
426 OPTGROUP_LOOP
, /* optinfo_flags */
427 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
428 ( PROP_cfg
| PROP_ssa
), /* properties_required */
429 0, /* properties_provided */
430 0, /* properties_destroyed */
431 0, /* todo_flags_start */
432 0, /* todo_flags_finish */
435 class pass_graphite_transforms
: public gimple_opt_pass
438 pass_graphite_transforms (gcc::context
*ctxt
)
439 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
442 /* opt_pass methods: */
443 virtual bool gate (function
*) { return gate_graphite_transforms (); }
444 virtual unsigned int execute (function
*fun
) { return graphite_transforms (fun
); }
446 }; // class pass_graphite_transforms
451 make_pass_graphite_transforms (gcc::context
*ctxt
)
453 return new pass_graphite_transforms (ctxt
);