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
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. */
38 /* Workaround for GMP 5.1.3 bug, see PR56019. */
41 #include <isl/constraint.h>
44 #include <isl/options.h>
45 #include <isl/union_map.h>
49 #include "coretypes.h"
51 #include "diagnostic-core.h"
53 #include "tree-pass.h"
60 #include "fold-const.h"
61 #include "gimple-iterator.h"
63 #include "tree-ssa-loop.h"
64 #include "tree-data-ref.h"
65 #include "tree-scalar-evolution.h"
66 #include "graphite-poly.h"
68 #include "tree-parloops.h"
69 #include "tree-cfgcleanup.h"
70 #include "graphite-scop-detection.h"
71 #include "graphite-isl-ast-to-gimple.h"
72 #include "graphite-sese-to-poly.h"
74 /* Print global statistics to FILE. */
77 print_global_statistics (FILE* file
)
82 long n_conditions
= 0;
86 long n_p_conditions
= 0;
90 FOR_ALL_BB_FN (bb
, cfun
)
92 gimple_stmt_iterator psi
;
97 /* Ignore artificial surrounding loop. */
98 if (bb
== bb
->loop_father
->header
102 n_p_loops
+= bb
->count
;
105 if (EDGE_COUNT (bb
->succs
) > 1)
108 n_p_conditions
+= bb
->count
;
111 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
114 n_p_stmts
+= bb
->count
;
118 fprintf (file
, "\nGlobal statistics (");
119 fprintf (file
, "BBS:%ld, ", n_bbs
);
120 fprintf (file
, "LOOPS:%ld, ", n_loops
);
121 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
122 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
123 fprintf (file
, "\nGlobal profiling statistics (");
124 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
125 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
126 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
127 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
130 /* Print statistics for SCOP to FILE. */
133 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
138 long n_conditions
= 0;
142 long n_p_conditions
= 0;
146 FOR_ALL_BB_FN (bb
, cfun
)
148 gimple_stmt_iterator psi
;
149 loop_p loop
= bb
->loop_father
;
151 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
155 n_p_bbs
+= bb
->count
;
157 if (EDGE_COUNT (bb
->succs
) > 1)
160 n_p_conditions
+= bb
->count
;
163 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
166 n_p_stmts
+= bb
->count
;
169 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
172 n_p_loops
+= bb
->count
;
176 fprintf (file
, "\nSCoP statistics (");
177 fprintf (file
, "BBS:%ld, ", n_bbs
);
178 fprintf (file
, "LOOPS:%ld, ", n_loops
);
179 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
180 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
181 fprintf (file
, "\nSCoP profiling statistics (");
182 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
183 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
184 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
185 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
188 /* Print statistics for SCOPS to FILE. */
191 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
197 FOR_EACH_VEC_ELT (scops
, i
, scop
)
198 print_graphite_scop_statistics (file
, scop
);
201 /* Initialize graphite: when there are no loops returns false. */
204 graphite_initialize (isl_ctx
*ctx
)
206 if (number_of_loops (cfun
) <= 1
207 /* FIXME: This limit on the number of basic blocks of a function
208 should be removed when the SCOP detection is faster. */
209 || (n_basic_blocks_for_fn (cfun
) >
210 PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION
)))
212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
213 print_global_statistics (dump_file
);
220 recompute_all_dominators ();
221 initialize_original_copy_tables ();
223 if (dump_file
&& dump_flags
)
224 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
229 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
233 graphite_finalize (bool need_cfg_cleanup_p
)
235 if (need_cfg_cleanup_p
)
239 profile_status_for_fn (cfun
) = PROFILE_ABSENT
;
240 release_recorded_exits ();
241 tree_estimate_probability ();
244 free_original_copy_tables ();
246 if (dump_file
&& dump_flags
)
247 print_loops (dump_file
, 3);
250 isl_ctx
*the_isl_ctx
;
252 /* Perform a set of linear transforms on the loops of the current
256 graphite_transform_loops (void)
260 bool need_cfg_cleanup_p
= false;
261 vec
<scop_p
> scops
= vNULL
;
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 FOR_EACH_VEC_ELT (scops
, i
, scop
)
284 if (dbg_cnt (graphite_scop
))
287 build_poly_scop (scop
);
289 if (POLY_SCOP_P (scop
)
290 && apply_poly_transforms (scop
)
291 && graphite_regenerate_ast_isl (scop
))
292 need_cfg_cleanup_p
= true;
297 graphite_finalize (need_cfg_cleanup_p
);
302 #else /* If ISL is not available: #ifndef HAVE_isl. */
305 graphite_transform_loops (void)
307 sorry ("Graphite loop optimizations cannot be used (ISL is not available).");
314 graphite_transforms (struct function
*fun
)
316 if (number_of_loops (fun
) <= 1)
319 graphite_transform_loops ();
325 gate_graphite_transforms (void)
327 /* Enable -fgraphite pass if any one of the graphite optimization flags
330 || flag_loop_interchange
331 || flag_loop_strip_mine
332 || flag_graphite_identity
333 || flag_loop_parallelize_all
334 || flag_loop_optimize_isl
335 || flag_loop_unroll_jam
)
338 return flag_graphite
!= 0;
343 const pass_data pass_data_graphite
=
345 GIMPLE_PASS
, /* type */
346 "graphite0", /* name */
347 OPTGROUP_LOOP
, /* optinfo_flags */
348 TV_GRAPHITE
, /* tv_id */
349 ( PROP_cfg
| PROP_ssa
), /* properties_required */
350 0, /* properties_provided */
351 0, /* properties_destroyed */
352 0, /* todo_flags_start */
353 0, /* todo_flags_finish */
356 class pass_graphite
: public gimple_opt_pass
359 pass_graphite (gcc::context
*ctxt
)
360 : gimple_opt_pass (pass_data_graphite
, ctxt
)
363 /* opt_pass methods: */
364 virtual bool gate (function
*) { return gate_graphite_transforms (); }
366 }; // class pass_graphite
371 make_pass_graphite (gcc::context
*ctxt
)
373 return new pass_graphite (ctxt
);
378 const pass_data pass_data_graphite_transforms
=
380 GIMPLE_PASS
, /* type */
381 "graphite", /* name */
382 OPTGROUP_LOOP
, /* optinfo_flags */
383 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
384 ( PROP_cfg
| PROP_ssa
), /* properties_required */
385 0, /* properties_provided */
386 0, /* properties_destroyed */
387 0, /* todo_flags_start */
388 0, /* todo_flags_finish */
391 class pass_graphite_transforms
: public gimple_opt_pass
394 pass_graphite_transforms (gcc::context
*ctxt
)
395 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
398 /* opt_pass methods: */
399 virtual bool gate (function
*) { return gate_graphite_transforms (); }
400 virtual unsigned int execute (function
*fun
) { return graphite_transforms (fun
); }
402 }; // class pass_graphite_transforms
407 make_pass_graphite_transforms (gcc::context
*ctxt
)
409 return new pass_graphite_transforms (ctxt
);