1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010 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. */
37 #include "coretypes.h"
42 #include "basic-block.h"
43 #include "diagnostic.h"
44 #include "tree-flow.h"
46 #include "tree-dump.h"
49 #include "tree-chrec.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
52 #include "tree-pass.h"
53 #include "value-prof.h"
54 #include "pointer-set.h"
62 #include "cloog/cloog.h"
64 #include "graphite-ppl.h"
66 #include "graphite-poly.h"
67 #include "graphite-scop-detection.h"
68 #include "graphite-clast-to-gimple.h"
69 #include "graphite-sese-to-poly.h"
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 (VEC_length (edge, 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 (VEC_length (edge, 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, heap) *scops)
194 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
195 print_graphite_scop_statistics (file, scop);
198 /* Initialize graphite: when there are no loops returns false. */
201 graphite_initialize (void)
203 if (number_of_loops () <= 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);
214 recompute_all_dominators ();
215 initialize_original_copy_tables ();
218 if (dump_file && dump_flags)
219 dump_function_to_file (current_function_decl, dump_file, dump_flags);
224 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
228 graphite_finalize (bool need_cfg_cleanup_p)
230 if (need_cfg_cleanup_p)
234 profile_status = PROFILE_ABSENT;
235 release_recorded_exits ();
236 tree_estimate_probability ();
240 free_original_copy_tables ();
242 if (dump_file && dump_flags)
243 print_loops (dump_file, 3);
246 /* Perform a set of linear transforms on the loops of the current
250 graphite_transform_loops (void)
254 bool need_cfg_cleanup_p = false;
255 VEC (scop_p, heap) *scops = NULL;
256 htab_t bb_pbb_mapping;
259 if (!graphite_initialize ())
262 build_scops (&scops);
264 if (dump_file && (dump_flags & TDF_DETAILS))
266 print_graphite_statistics (dump_file, scops);
267 print_global_statistics (dump_file);
270 bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
271 reductions = sbitmap_alloc (last_basic_block * 2);
272 sbitmap_zero (reductions);
274 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
275 if (dbg_cnt (graphite_scop))
276 rewrite_commutative_reductions_out_of_ssa (SCOP_REGION (scop),
279 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
280 if (dbg_cnt (graphite_scop))
282 rewrite_reductions_out_of_ssa (scop);
283 build_scop_bbs (scop, reductions);
286 sbitmap_free (reductions);
288 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
289 if (dbg_cnt (graphite_scop))
290 build_poly_scop (scop);
292 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
293 if (POLY_SCOP_P (scop)
294 && apply_poly_transforms (scop)
295 && gloog (scop, bb_pbb_mapping))
296 need_cfg_cleanup_p = true;
298 htab_delete (bb_pbb_mapping);
300 graphite_finalize (need_cfg_cleanup_p);
303 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
306 graphite_transform_loops (void)
308 sorry ("Graphite loop optimizations cannot be used");