]>
Commit | Line | Data |
---|---|---|
255b6be7 | 1 | /* Gimple Represented as Polyhedra. |
7cf0dbf3 | 2 | Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
255b6be7 | 3 | Contributed by Sebastian Pop <sebastian.pop@inria.fr>. |
4 | ||
5 | This file is part of GCC. | |
6 | ||
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) | |
10 | any later version. | |
11 | ||
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. | |
16 | ||
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/>. */ | |
20 | ||
21 | /* This pass converts GIMPLE to GRAPHITE, performs some loop | |
22 | transformations and then converts the resulting representation back | |
26c166eb | 23 | to GIMPLE. |
255b6be7 | 24 | |
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 | |
26c166eb | 28 | the related work. |
255b6be7 | 29 | |
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. */ | |
34 | ||
35 | #include "config.h" | |
36 | #include "system.h" | |
37 | #include "coretypes.h" | |
38 | #include "tm.h" | |
39 | #include "ggc.h" | |
40 | #include "tree.h" | |
41 | #include "rtl.h" | |
42 | #include "basic-block.h" | |
43 | #include "diagnostic.h" | |
44 | #include "tree-flow.h" | |
255b6be7 | 45 | #include "tree-dump.h" |
46 | #include "timevar.h" | |
47 | #include "cfgloop.h" | |
48 | #include "tree-chrec.h" | |
49 | #include "tree-data-ref.h" | |
50 | #include "tree-scalar-evolution.h" | |
51 | #include "tree-pass.h" | |
899e6126 | 52 | #include "value-prof.h" |
255b6be7 | 53 | #include "pointer-set.h" |
54 | #include "gimple.h" | |
26c166eb | 55 | #include "sese.h" |
675d86b2 | 56 | #include "predict.h" |
e819c864 | 57 | #include "dbgcnt.h" |
255b6be7 | 58 | |
59 | #ifdef HAVE_cloog | |
d970c7fe | 60 | |
255b6be7 | 61 | #include "cloog/cloog.h" |
26c166eb | 62 | #include "ppl_c.h" |
f0fc00f2 | 63 | #include "graphite-cloog-compat.h" |
26c166eb | 64 | #include "graphite-ppl.h" |
255b6be7 | 65 | #include "graphite.h" |
26c166eb | 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" | |
255b6be7 | 70 | |
26c166eb | 71 | /* Print global statistics to FILE. */ |
7d3f5847 | 72 | |
73 | static void | |
26c166eb | 74 | print_global_statistics (FILE* file) |
7d3f5847 | 75 | { |
26c166eb | 76 | long n_bbs = 0; |
77 | long n_loops = 0; | |
78 | long n_stmts = 0; | |
79 | long n_conditions = 0; | |
80 | long n_p_bbs = 0; | |
81 | long n_p_loops = 0; | |
82 | long n_p_stmts = 0; | |
83 | long n_p_conditions = 0; | |
7d3f5847 | 84 | |
26c166eb | 85 | basic_block bb; |
7d3f5847 | 86 | |
26c166eb | 87 | FOR_ALL_BB (bb) |
88 | { | |
89 | gimple_stmt_iterator psi; | |
7d3f5847 | 90 | |
26c166eb | 91 | n_bbs++; |
92 | n_p_bbs += bb->count; | |
7d3f5847 | 93 | |
26c166eb | 94 | /* Ignore artificial surrounding loop. */ |
95 | if (bb == bb->loop_father->header | |
96 | && bb->index != 0) | |
7d3f5847 | 97 | { |
26c166eb | 98 | n_loops++; |
99 | n_p_loops += bb->count; | |
7d3f5847 | 100 | } |
7d3f5847 | 101 | |
26c166eb | 102 | if (VEC_length (edge, bb->succs) > 1) |
103 | { | |
104 | n_conditions++; | |
105 | n_p_conditions += bb->count; | |
106 | } | |
7d3f5847 | 107 | |
26c166eb | 108 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
109 | { | |
110 | n_stmts++; | |
111 | n_p_stmts += bb->count; | |
112 | } | |
7d3f5847 | 113 | } |
114 | ||
26c166eb | 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); | |
255b6be7 | 125 | } |
126 | ||
26c166eb | 127 | /* Print statistics for SCOP to FILE. */ |
255b6be7 | 128 | |
129 | static void | |
26c166eb | 130 | print_graphite_scop_statistics (FILE* file, scop_p scop) |
255b6be7 | 131 | { |
26c166eb | 132 | long n_bbs = 0; |
133 | long n_loops = 0; | |
134 | long n_stmts = 0; | |
135 | long n_conditions = 0; | |
136 | long n_p_bbs = 0; | |
137 | long n_p_loops = 0; | |
138 | long n_p_stmts = 0; | |
139 | long n_p_conditions = 0; | |
255b6be7 | 140 | |
26c166eb | 141 | basic_block bb; |
255b6be7 | 142 | |
26c166eb | 143 | FOR_ALL_BB (bb) |
255b6be7 | 144 | { |
26c166eb | 145 | gimple_stmt_iterator psi; |
146 | loop_p loop = bb->loop_father; | |
255b6be7 | 147 | |
26c166eb | 148 | if (!bb_in_sese_p (bb, SCOP_REGION (scop))) |
149 | continue; | |
255b6be7 | 150 | |
26c166eb | 151 | n_bbs++; |
152 | n_p_bbs += bb->count; | |
255b6be7 | 153 | |
26c166eb | 154 | if (VEC_length (edge, bb->succs) > 1) |
255b6be7 | 155 | { |
26c166eb | 156 | n_conditions++; |
157 | n_p_conditions += bb->count; | |
255b6be7 | 158 | } |
255b6be7 | 159 | |
26c166eb | 160 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
255b6be7 | 161 | { |
26c166eb | 162 | n_stmts++; |
163 | n_p_stmts += bb->count; | |
255b6be7 | 164 | } |
255b6be7 | 165 | |
26c166eb | 166 | if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) |
167 | { | |
168 | n_loops++; | |
169 | n_p_loops += bb->count; | |
170 | } | |
171 | } | |
145bdf6a | 172 | |
26c166eb | 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); | |
255b6be7 | 183 | } |
184 | ||
26c166eb | 185 | /* Print statistics for SCOPS to FILE. */ |
255b6be7 | 186 | |
26c166eb | 187 | static void |
188 | print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops) | |
255b6be7 | 189 | { |
255b6be7 | 190 | int i; |
255b6be7 | 191 | |
26c166eb | 192 | scop_p scop; |
255b6be7 | 193 | |
48148244 | 194 | FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
26c166eb | 195 | print_graphite_scop_statistics (file, scop); |
255b6be7 | 196 | } |
197 | ||
26c166eb | 198 | /* Initialize graphite: when there are no loops returns false. */ |
255b6be7 | 199 | |
200 | static bool | |
26c166eb | 201 | graphite_initialize (void) |
255b6be7 | 202 | { |
f0fc00f2 | 203 | int ppl_initialized; |
204 | ||
ef98ee10 | 205 | if (number_of_loops () <= 1 |
206 | /* FIXME: This limit on the number of basic blocks of a function | |
207 | should be removed when the SCOP detection is faster. */ | |
94ba21de | 208 | || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)) |
255b6be7 | 209 | { |
26c166eb | 210 | if (dump_file && (dump_flags & TDF_DETAILS)) |
211 | print_global_statistics (dump_file); | |
255b6be7 | 212 | |
26c166eb | 213 | return false; |
255b6be7 | 214 | } |
215 | ||
d4d6f501 | 216 | scev_reset (); |
26c166eb | 217 | recompute_all_dominators (); |
218 | initialize_original_copy_tables (); | |
f0fc00f2 | 219 | |
220 | ppl_initialized = ppl_initialize (); | |
221 | gcc_assert (ppl_initialized == 0); | |
222 | ||
26c166eb | 223 | cloog_initialize (); |
255b6be7 | 224 | |
26c166eb | 225 | if (dump_file && dump_flags) |
226 | dump_function_to_file (current_function_decl, dump_file, dump_flags); | |
255b6be7 | 227 | |
26c166eb | 228 | return true; |
255b6be7 | 229 | } |
230 | ||
26c166eb | 231 | /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is |
232 | true. */ | |
255b6be7 | 233 | |
234 | static void | |
26c166eb | 235 | graphite_finalize (bool need_cfg_cleanup_p) |
255b6be7 | 236 | { |
26c166eb | 237 | if (need_cfg_cleanup_p) |
675d86b2 | 238 | { |
d9458edc | 239 | scev_reset (); |
675d86b2 | 240 | cleanup_tree_cfg (); |
241 | profile_status = PROFILE_ABSENT; | |
242 | release_recorded_exits (); | |
243 | tree_estimate_probability (); | |
244 | } | |
255b6be7 | 245 | |
26c166eb | 246 | cloog_finalize (); |
f0fc00f2 | 247 | ppl_finalize (); |
26c166eb | 248 | free_original_copy_tables (); |
d0483ac6 | 249 | |
26c166eb | 250 | if (dump_file && dump_flags) |
251 | print_loops (dump_file, 3); | |
255b6be7 | 252 | } |
253 | ||
254 | /* Perform a set of linear transforms on the loops of the current | |
255 | function. */ | |
256 | ||
257 | void | |
258 | graphite_transform_loops (void) | |
259 | { | |
260 | int i; | |
261 | scop_p scop; | |
26c166eb | 262 | bool need_cfg_cleanup_p = false; |
263 | VEC (scop_p, heap) *scops = NULL; | |
264 | htab_t bb_pbb_mapping; | |
5d2603f9 | 265 | sbitmap reductions; |
255b6be7 | 266 | |
26c166eb | 267 | if (!graphite_initialize ()) |
255b6be7 | 268 | return; |
269 | ||
26c166eb | 270 | build_scops (&scops); |
255b6be7 | 271 | |
272 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
255b6be7 | 273 | { |
26c166eb | 274 | print_graphite_statistics (dump_file, scops); |
275 | print_global_statistics (dump_file); | |
276 | } | |
35fb1eb0 | 277 | |
26c166eb | 278 | bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free); |
5d2603f9 | 279 | reductions = sbitmap_alloc (last_basic_block * 2); |
280 | sbitmap_zero (reductions); | |
281 | ||
48148244 | 282 | FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
e819c864 | 283 | if (dbg_cnt (graphite_scop)) |
284 | rewrite_commutative_reductions_out_of_ssa (SCOP_REGION (scop), | |
285 | reductions); | |
5d2603f9 | 286 | |
48148244 | 287 | FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
e819c864 | 288 | if (dbg_cnt (graphite_scop)) |
289 | { | |
290 | rewrite_reductions_out_of_ssa (scop); | |
bf8b5699 | 291 | rewrite_cross_bb_scalar_deps_out_of_ssa (scop); |
e819c864 | 292 | build_scop_bbs (scop, reductions); |
293 | } | |
5d2603f9 | 294 | |
295 | sbitmap_free (reductions); | |
255b6be7 | 296 | |
48148244 | 297 | FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
e819c864 | 298 | if (dbg_cnt (graphite_scop)) |
299 | build_poly_scop (scop); | |
255b6be7 | 300 | |
48148244 | 301 | FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
94bdcd77 | 302 | if (POLY_SCOP_P (scop) |
303 | && apply_poly_transforms (scop) | |
93206bb0 | 304 | && gloog (scop, bb_pbb_mapping)) |
94bdcd77 | 305 | need_cfg_cleanup_p = true; |
255b6be7 | 306 | |
26c166eb | 307 | htab_delete (bb_pbb_mapping); |
308 | free_scops (scops); | |
309 | graphite_finalize (need_cfg_cleanup_p); | |
255b6be7 | 310 | } |
311 | ||
312 | #else /* If Cloog is not available: #ifndef HAVE_cloog. */ | |
313 | ||
314 | void | |
315 | graphite_transform_loops (void) | |
316 | { | |
255b6be7 | 317 | sorry ("Graphite loop optimizations cannot be used"); |
318 | } | |
319 | ||
320 | #endif |