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>
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 "basic-block.h"
52 #include "tree-ssa-alias.h"
53 #include "internal-fn.h"
54 #include "gimple-expr.h"
57 #include "gimple-iterator.h"
59 #include "tree-ssa-loop.h"
60 #include "tree-dump.h"
62 #include "tree-chrec.h"
63 #include "tree-data-ref.h"
64 #include "tree-scalar-evolution.h"
67 #include "tree-parloops.h"
68 #include "tree-pass.h"
69 #include "tree-cfgcleanup.h"
73 #include "graphite-poly.h"
74 #include "graphite-scop-detection.h"
75 #include "graphite-clast-to-gimple.h"
76 #include "graphite-sese-to-poly.h"
77 #include "graphite-htab.h"
79 CloogState
*cloog_state
;
81 /* Print global statistics to FILE. */
84 print_global_statistics (FILE* file
)
89 long n_conditions
= 0;
93 long n_p_conditions
= 0;
97 FOR_ALL_BB_FN (bb
, cfun
)
99 gimple_stmt_iterator psi
;
102 n_p_bbs
+= bb
->count
;
104 /* Ignore artificial surrounding loop. */
105 if (bb
== bb
->loop_father
->header
109 n_p_loops
+= bb
->count
;
112 if (EDGE_COUNT (bb
->succs
) > 1)
115 n_p_conditions
+= bb
->count
;
118 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
121 n_p_stmts
+= bb
->count
;
125 fprintf (file
, "\nGlobal statistics (");
126 fprintf (file
, "BBS:%ld, ", n_bbs
);
127 fprintf (file
, "LOOPS:%ld, ", n_loops
);
128 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
129 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
130 fprintf (file
, "\nGlobal profiling statistics (");
131 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
132 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
133 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
134 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
137 /* Print statistics for SCOP to FILE. */
140 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
145 long n_conditions
= 0;
149 long n_p_conditions
= 0;
153 FOR_ALL_BB_FN (bb
, cfun
)
155 gimple_stmt_iterator psi
;
156 loop_p loop
= bb
->loop_father
;
158 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
162 n_p_bbs
+= bb
->count
;
164 if (EDGE_COUNT (bb
->succs
) > 1)
167 n_p_conditions
+= bb
->count
;
170 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
173 n_p_stmts
+= bb
->count
;
176 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
179 n_p_loops
+= bb
->count
;
183 fprintf (file
, "\nSCoP statistics (");
184 fprintf (file
, "BBS:%ld, ", n_bbs
);
185 fprintf (file
, "LOOPS:%ld, ", n_loops
);
186 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
187 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
188 fprintf (file
, "\nSCoP profiling statistics (");
189 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
190 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
191 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
192 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
195 /* Print statistics for SCOPS to FILE. */
198 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
204 FOR_EACH_VEC_ELT (scops
, i
, scop
)
205 print_graphite_scop_statistics (file
, scop
);
208 /* Initialize graphite: when there are no loops returns false. */
211 graphite_initialize (isl_ctx
*ctx
)
213 if (number_of_loops (cfun
) <= 1
214 /* FIXME: This limit on the number of basic blocks of a function
215 should be removed when the SCOP detection is faster. */
216 || (n_basic_blocks_for_fn (cfun
) >
217 PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION
)))
219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
220 print_global_statistics (dump_file
);
227 recompute_all_dominators ();
228 initialize_original_copy_tables ();
230 cloog_state
= cloog_isl_state_malloc (ctx
);
232 if (dump_file
&& dump_flags
)
233 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
238 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
242 graphite_finalize (bool need_cfg_cleanup_p
)
244 if (need_cfg_cleanup_p
)
248 profile_status_for_fn (cfun
) = PROFILE_ABSENT
;
249 release_recorded_exits ();
250 tree_estimate_probability ();
253 cloog_state_free (cloog_state
);
254 free_original_copy_tables ();
256 if (dump_file
&& dump_flags
)
257 print_loops (dump_file
, 3);
260 isl_ctx
*the_isl_ctx
;
262 /* Perform a set of linear transforms on the loops of the current
266 graphite_transform_loops (void)
270 bool need_cfg_cleanup_p
= false;
271 vec
<scop_p
> scops
= vNULL
;
274 /* If a function is parallel it was most probably already run through graphite
275 once. No need to run again. */
276 if (parallelized_function_p (cfun
->decl
))
279 ctx
= isl_ctx_alloc ();
280 isl_options_set_on_error (ctx
, ISL_ON_ERROR_ABORT
);
281 if (!graphite_initialize (ctx
))
285 build_scops (&scops
);
287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
289 print_graphite_statistics (dump_file
, scops
);
290 print_global_statistics (dump_file
);
293 bb_pbb_htab_type
bb_pbb_mapping (10);
294 FOR_EACH_VEC_ELT (scops
, i
, scop
)
295 if (dbg_cnt (graphite_scop
))
298 build_poly_scop (scop
);
300 if (POLY_SCOP_P (scop
)
301 && apply_poly_transforms (scop
)
302 && gloog (scop
, &bb_pbb_mapping
))
303 need_cfg_cleanup_p
= true;
307 graphite_finalize (need_cfg_cleanup_p
);
312 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
315 graphite_transform_loops (void)
317 sorry ("Graphite loop optimizations cannot be used");
324 graphite_transforms (struct function
*fun
)
326 if (number_of_loops (fun
) <= 1)
329 graphite_transform_loops ();
335 gate_graphite_transforms (void)
337 /* Enable -fgraphite pass if any one of the graphite optimization flags
340 || flag_loop_interchange
341 || flag_loop_strip_mine
342 || flag_graphite_identity
343 || flag_loop_parallelize_all
344 || flag_loop_optimize_isl
)
347 return flag_graphite
!= 0;
352 const pass_data pass_data_graphite
=
354 GIMPLE_PASS
, /* type */
355 "graphite0", /* name */
356 OPTGROUP_LOOP
, /* optinfo_flags */
357 false, /* has_execute */
358 TV_GRAPHITE
, /* tv_id */
359 ( PROP_cfg
| PROP_ssa
), /* properties_required */
360 0, /* properties_provided */
361 0, /* properties_destroyed */
362 0, /* todo_flags_start */
363 0, /* todo_flags_finish */
366 class pass_graphite
: public gimple_opt_pass
369 pass_graphite (gcc::context
*ctxt
)
370 : gimple_opt_pass (pass_data_graphite
, ctxt
)
373 /* opt_pass methods: */
374 virtual bool gate (function
*) { return gate_graphite_transforms (); }
376 }; // class pass_graphite
381 make_pass_graphite (gcc::context
*ctxt
)
383 return new pass_graphite (ctxt
);
388 const pass_data pass_data_graphite_transforms
=
390 GIMPLE_PASS
, /* type */
391 "graphite", /* name */
392 OPTGROUP_LOOP
, /* optinfo_flags */
393 true, /* has_execute */
394 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
395 ( PROP_cfg
| PROP_ssa
), /* properties_required */
396 0, /* properties_provided */
397 0, /* properties_destroyed */
398 0, /* todo_flags_start */
399 0, /* todo_flags_finish */
402 class pass_graphite_transforms
: public gimple_opt_pass
405 pass_graphite_transforms (gcc::context
*ctxt
)
406 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
409 /* opt_pass methods: */
410 virtual bool gate (function
*) { return gate_graphite_transforms (); }
411 virtual unsigned int execute (function
*fun
) { return graphite_transforms (fun
); }
413 }; // class pass_graphite_transforms
418 make_pass_graphite_transforms (gcc::context
*ctxt
)
420 return new pass_graphite_transforms (ctxt
);