1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2014 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>
43 #include <cloog/cloog.h>
44 #include <cloog/isl/domain.h>
45 #include <cloog/isl/cloog.h>
50 #include "coretypes.h"
51 #include "diagnostic-core.h"
59 #include "hard-reg-set.h"
62 #include "dominance.h"
64 #include "basic-block.h"
65 #include "tree-ssa-alias.h"
66 #include "internal-fn.h"
67 #include "gimple-expr.h"
70 #include "gimple-iterator.h"
72 #include "tree-ssa-loop.h"
73 #include "tree-dump.h"
75 #include "tree-chrec.h"
76 #include "tree-data-ref.h"
77 #include "tree-scalar-evolution.h"
80 #include "tree-parloops.h"
81 #include "tree-pass.h"
82 #include "tree-cfgcleanup.h"
86 #include "graphite-poly.h"
87 #include "graphite-scop-detection.h"
88 #include "graphite-isl-ast-to-gimple.h"
89 #include "graphite-sese-to-poly.h"
90 #include "graphite-htab.h"
93 #include "graphite-clast-to-gimple.h"
95 CloogState
*cloog_state
;
98 /* Print global statistics to FILE. */
101 print_global_statistics (FILE* file
)
106 long n_conditions
= 0;
110 long n_p_conditions
= 0;
114 FOR_ALL_BB_FN (bb
, cfun
)
116 gimple_stmt_iterator psi
;
119 n_p_bbs
+= bb
->count
;
121 /* Ignore artificial surrounding loop. */
122 if (bb
== bb
->loop_father
->header
126 n_p_loops
+= bb
->count
;
129 if (EDGE_COUNT (bb
->succs
) > 1)
132 n_p_conditions
+= bb
->count
;
135 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
138 n_p_stmts
+= bb
->count
;
142 fprintf (file
, "\nGlobal statistics (");
143 fprintf (file
, "BBS:%ld, ", n_bbs
);
144 fprintf (file
, "LOOPS:%ld, ", n_loops
);
145 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
146 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
147 fprintf (file
, "\nGlobal profiling statistics (");
148 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
149 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
150 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
151 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
154 /* Print statistics for SCOP to FILE. */
157 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
162 long n_conditions
= 0;
166 long n_p_conditions
= 0;
170 FOR_ALL_BB_FN (bb
, cfun
)
172 gimple_stmt_iterator psi
;
173 loop_p loop
= bb
->loop_father
;
175 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
179 n_p_bbs
+= bb
->count
;
181 if (EDGE_COUNT (bb
->succs
) > 1)
184 n_p_conditions
+= bb
->count
;
187 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
190 n_p_stmts
+= bb
->count
;
193 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
196 n_p_loops
+= bb
->count
;
200 fprintf (file
, "\nSCoP statistics (");
201 fprintf (file
, "BBS:%ld, ", n_bbs
);
202 fprintf (file
, "LOOPS:%ld, ", n_loops
);
203 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
204 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
205 fprintf (file
, "\nSCoP profiling statistics (");
206 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
207 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
208 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
209 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
212 /* Print statistics for SCOPS to FILE. */
215 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
221 FOR_EACH_VEC_ELT (scops
, i
, scop
)
222 print_graphite_scop_statistics (file
, scop
);
225 /* Initialize graphite: when there are no loops returns false. */
228 graphite_initialize (isl_ctx
*ctx
)
230 if (number_of_loops (cfun
) <= 1
231 /* FIXME: This limit on the number of basic blocks of a function
232 should be removed when the SCOP detection is faster. */
233 || (n_basic_blocks_for_fn (cfun
) >
234 PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION
)))
236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
237 print_global_statistics (dump_file
);
244 recompute_all_dominators ();
245 initialize_original_copy_tables ();
248 cloog_state
= cloog_isl_state_malloc (ctx
);
251 if (dump_file
&& dump_flags
)
252 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
257 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
261 graphite_finalize (bool need_cfg_cleanup_p
)
263 if (need_cfg_cleanup_p
)
267 profile_status_for_fn (cfun
) = PROFILE_ABSENT
;
268 release_recorded_exits ();
269 tree_estimate_probability ();
273 cloog_state_free (cloog_state
);
275 free_original_copy_tables ();
277 if (dump_file
&& dump_flags
)
278 print_loops (dump_file
, 3);
281 isl_ctx
*the_isl_ctx
;
283 /* Perform a set of linear transforms on the loops of the current
287 graphite_transform_loops (void)
291 bool need_cfg_cleanup_p
= false;
292 vec
<scop_p
> scops
= vNULL
;
295 /* If a function is parallel it was most probably already run through graphite
296 once. No need to run again. */
297 if (parallelized_function_p (cfun
->decl
))
300 ctx
= isl_ctx_alloc ();
301 isl_options_set_on_error (ctx
, ISL_ON_ERROR_ABORT
);
302 if (!graphite_initialize (ctx
))
306 build_scops (&scops
);
308 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
310 print_graphite_statistics (dump_file
, scops
);
311 print_global_statistics (dump_file
);
314 bb_pbb_htab_type
bb_pbb_mapping (10);
317 if(flag_graphite_code_gen
== FGRAPHITE_CODE_GEN_CLOOG
)
319 flag_graphite_code_gen
= FGRAPHITE_CODE_GEN_ISL
;
320 printf ("The CLooG code generator cannot be used (CLooG is not "
321 "available). The ISL code generator was chosen.\n");
325 FOR_EACH_VEC_ELT (scops
, i
, scop
)
326 if (dbg_cnt (graphite_scop
))
329 build_poly_scop (scop
);
332 if (POLY_SCOP_P (scop
)
333 && apply_poly_transforms (scop
)
334 && (((flag_graphite_code_gen
== FGRAPHITE_CODE_GEN_ISL
)
335 && graphite_regenerate_ast_isl (scop
))
336 || ((flag_graphite_code_gen
== FGRAPHITE_CODE_GEN_CLOOG
)
337 && graphite_regenerate_ast_cloog (scop
, &bb_pbb_mapping
))))
338 need_cfg_cleanup_p
= true;
340 if (POLY_SCOP_P (scop
)
341 && apply_poly_transforms (scop
)
342 && graphite_regenerate_ast_isl (scop
))
343 need_cfg_cleanup_p
= true;
349 graphite_finalize (need_cfg_cleanup_p
);
354 #else /* If ISL is not available: #ifndef HAVE_isl. */
357 graphite_transform_loops (void)
359 sorry ("Graphite loop optimizations cannot be used (ISL is not available).");
366 graphite_transforms (struct function
*fun
)
368 if (number_of_loops (fun
) <= 1)
371 graphite_transform_loops ();
377 gate_graphite_transforms (void)
379 /* Enable -fgraphite pass if any one of the graphite optimization flags
382 || flag_loop_interchange
383 || flag_loop_strip_mine
384 || flag_graphite_identity
385 || flag_loop_parallelize_all
386 || flag_loop_optimize_isl
)
389 return flag_graphite
!= 0;
394 const pass_data pass_data_graphite
=
396 GIMPLE_PASS
, /* type */
397 "graphite0", /* name */
398 OPTGROUP_LOOP
, /* optinfo_flags */
399 TV_GRAPHITE
, /* tv_id */
400 ( PROP_cfg
| PROP_ssa
), /* properties_required */
401 0, /* properties_provided */
402 0, /* properties_destroyed */
403 0, /* todo_flags_start */
404 0, /* todo_flags_finish */
407 class pass_graphite
: public gimple_opt_pass
410 pass_graphite (gcc::context
*ctxt
)
411 : gimple_opt_pass (pass_data_graphite
, ctxt
)
414 /* opt_pass methods: */
415 virtual bool gate (function
*) { return gate_graphite_transforms (); }
417 }; // class pass_graphite
422 make_pass_graphite (gcc::context
*ctxt
)
424 return new pass_graphite (ctxt
);
429 const pass_data pass_data_graphite_transforms
=
431 GIMPLE_PASS
, /* type */
432 "graphite", /* name */
433 OPTGROUP_LOOP
, /* optinfo_flags */
434 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
435 ( PROP_cfg
| PROP_ssa
), /* properties_required */
436 0, /* properties_provided */
437 0, /* properties_destroyed */
438 0, /* todo_flags_start */
439 0, /* todo_flags_finish */
442 class pass_graphite_transforms
: public gimple_opt_pass
445 pass_graphite_transforms (gcc::context
*ctxt
)
446 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
449 /* opt_pass methods: */
450 virtual bool gate (function
*) { return gate_graphite_transforms (); }
451 virtual unsigned int execute (function
*fun
) { return graphite_transforms (fun
); }
453 }; // class pass_graphite_transforms
458 make_pass_graphite_transforms (gcc::context
*ctxt
)
460 return new pass_graphite_transforms (ctxt
);