]>
Commit | Line | Data |
---|---|---|
f8bf9252 | 1 | /* Gimple Represented as Polyhedra. |
33ad93b9 RG |
2 | Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011 |
3 | Free Software Foundation, Inc. | |
f8bf9252 SP |
4 | Contributed by Sebastian Pop <sebastian.pop@inria.fr>. |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | /* This pass converts GIMPLE to GRAPHITE, performs some loop | |
23 | transformations and then converts the resulting representation back | |
204b560f | 24 | to GIMPLE. |
f8bf9252 SP |
25 | |
26 | An early description of this pass can be found in the GCC Summit'06 | |
27 | paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC". | |
28 | The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to | |
204b560f | 29 | the related work. |
f8bf9252 SP |
30 | |
31 | One important document to read is CLooG's internal manual: | |
32 | http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD | |
33 | that describes the data structure of loops used in this file, and | |
34 | the functions that are used for transforming the code. */ | |
35 | ||
36 | #include "config.h" | |
33ad93b9 RG |
37 | |
38 | #ifdef HAVE_cloog | |
39 | #include <isl/set.h> | |
40 | #include <isl/map.h> | |
41 | #include <isl/options.h> | |
42 | #include <isl/union_map.h> | |
43 | #include <cloog/cloog.h> | |
44 | #include <cloog/isl/domain.h> | |
45 | #include <cloog/isl/cloog.h> | |
46 | #endif | |
47 | ||
f8bf9252 SP |
48 | #include "system.h" |
49 | #include "coretypes.h" | |
32a73fc4 | 50 | #include "diagnostic-core.h" |
f8bf9252 | 51 | #include "tree-flow.h" |
f8bf9252 | 52 | #include "tree-dump.h" |
f8bf9252 SP |
53 | #include "cfgloop.h" |
54 | #include "tree-chrec.h" | |
55 | #include "tree-data-ref.h" | |
56 | #include "tree-scalar-evolution.h" | |
204b560f | 57 | #include "sese.h" |
6a7441f5 | 58 | #include "dbgcnt.h" |
f8bf9252 SP |
59 | |
60 | #ifdef HAVE_cloog | |
bcbe3b25 | 61 | |
204b560f SP |
62 | #include "graphite-poly.h" |
63 | #include "graphite-scop-detection.h" | |
64 | #include "graphite-clast-to-gimple.h" | |
65 | #include "graphite-sese-to-poly.h" | |
f8bf9252 | 66 | |
57d598f7 SP |
67 | CloogState *cloog_state; |
68 | ||
204b560f | 69 | /* Print global statistics to FILE. */ |
4d6c7237 SP |
70 | |
71 | static void | |
204b560f | 72 | print_global_statistics (FILE* file) |
4d6c7237 | 73 | { |
204b560f SP |
74 | long n_bbs = 0; |
75 | long n_loops = 0; | |
76 | long n_stmts = 0; | |
77 | long n_conditions = 0; | |
78 | long n_p_bbs = 0; | |
79 | long n_p_loops = 0; | |
80 | long n_p_stmts = 0; | |
81 | long n_p_conditions = 0; | |
4d6c7237 | 82 | |
204b560f | 83 | basic_block bb; |
4d6c7237 | 84 | |
204b560f SP |
85 | FOR_ALL_BB (bb) |
86 | { | |
87 | gimple_stmt_iterator psi; | |
4d6c7237 | 88 | |
204b560f SP |
89 | n_bbs++; |
90 | n_p_bbs += bb->count; | |
4d6c7237 | 91 | |
204b560f SP |
92 | /* Ignore artificial surrounding loop. */ |
93 | if (bb == bb->loop_father->header | |
94 | && bb->index != 0) | |
4d6c7237 | 95 | { |
204b560f SP |
96 | n_loops++; |
97 | n_p_loops += bb->count; | |
4d6c7237 | 98 | } |
4d6c7237 | 99 | |
204b560f SP |
100 | if (VEC_length (edge, bb->succs) > 1) |
101 | { | |
102 | n_conditions++; | |
103 | n_p_conditions += bb->count; | |
104 | } | |
4d6c7237 | 105 | |
204b560f SP |
106 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
107 | { | |
108 | n_stmts++; | |
109 | n_p_stmts += bb->count; | |
110 | } | |
4d6c7237 SP |
111 | } |
112 | ||
204b560f SP |
113 | fprintf (file, "\nGlobal statistics ("); |
114 | fprintf (file, "BBS:%ld, ", n_bbs); | |
115 | fprintf (file, "LOOPS:%ld, ", n_loops); | |
116 | fprintf (file, "CONDITIONS:%ld, ", n_conditions); | |
117 | fprintf (file, "STMTS:%ld)\n", n_stmts); | |
118 | fprintf (file, "\nGlobal profiling statistics ("); | |
119 | fprintf (file, "BBS:%ld, ", n_p_bbs); | |
120 | fprintf (file, "LOOPS:%ld, ", n_p_loops); | |
121 | fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); | |
122 | fprintf (file, "STMTS:%ld)\n", n_p_stmts); | |
f8bf9252 SP |
123 | } |
124 | ||
204b560f | 125 | /* Print statistics for SCOP to FILE. */ |
f8bf9252 SP |
126 | |
127 | static void | |
204b560f | 128 | print_graphite_scop_statistics (FILE* file, scop_p scop) |
f8bf9252 | 129 | { |
204b560f SP |
130 | long n_bbs = 0; |
131 | long n_loops = 0; | |
132 | long n_stmts = 0; | |
133 | long n_conditions = 0; | |
134 | long n_p_bbs = 0; | |
135 | long n_p_loops = 0; | |
136 | long n_p_stmts = 0; | |
137 | long n_p_conditions = 0; | |
f8bf9252 | 138 | |
204b560f | 139 | basic_block bb; |
f8bf9252 | 140 | |
204b560f | 141 | FOR_ALL_BB (bb) |
f8bf9252 | 142 | { |
204b560f SP |
143 | gimple_stmt_iterator psi; |
144 | loop_p loop = bb->loop_father; | |
f8bf9252 | 145 | |
204b560f SP |
146 | if (!bb_in_sese_p (bb, SCOP_REGION (scop))) |
147 | continue; | |
f8bf9252 | 148 | |
204b560f SP |
149 | n_bbs++; |
150 | n_p_bbs += bb->count; | |
f8bf9252 | 151 | |
204b560f | 152 | if (VEC_length (edge, bb->succs) > 1) |
f8bf9252 | 153 | { |
204b560f SP |
154 | n_conditions++; |
155 | n_p_conditions += bb->count; | |
f8bf9252 | 156 | } |
f8bf9252 | 157 | |
204b560f | 158 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
f8bf9252 | 159 | { |
204b560f SP |
160 | n_stmts++; |
161 | n_p_stmts += bb->count; | |
f8bf9252 | 162 | } |
f8bf9252 | 163 | |
204b560f SP |
164 | if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) |
165 | { | |
166 | n_loops++; | |
167 | n_p_loops += bb->count; | |
168 | } | |
169 | } | |
6a114766 | 170 | |
204b560f SP |
171 | fprintf (file, "\nSCoP statistics ("); |
172 | fprintf (file, "BBS:%ld, ", n_bbs); | |
173 | fprintf (file, "LOOPS:%ld, ", n_loops); | |
174 | fprintf (file, "CONDITIONS:%ld, ", n_conditions); | |
175 | fprintf (file, "STMTS:%ld)\n", n_stmts); | |
176 | fprintf (file, "\nSCoP profiling statistics ("); | |
177 | fprintf (file, "BBS:%ld, ", n_p_bbs); | |
178 | fprintf (file, "LOOPS:%ld, ", n_p_loops); | |
179 | fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); | |
180 | fprintf (file, "STMTS:%ld)\n", n_p_stmts); | |
f8bf9252 SP |
181 | } |
182 | ||
204b560f | 183 | /* Print statistics for SCOPS to FILE. */ |
f8bf9252 | 184 | |
204b560f SP |
185 | static void |
186 | print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops) | |
f8bf9252 | 187 | { |
f8bf9252 | 188 | int i; |
f8bf9252 | 189 | |
204b560f | 190 | scop_p scop; |
f8bf9252 | 191 | |
ac47786e | 192 | FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
204b560f | 193 | print_graphite_scop_statistics (file, scop); |
f8bf9252 SP |
194 | } |
195 | ||
204b560f | 196 | /* Initialize graphite: when there are no loops returns false. */ |
f8bf9252 SP |
197 | |
198 | static bool | |
33ad93b9 | 199 | graphite_initialize (isl_ctx *ctx) |
f8bf9252 | 200 | { |
9bf13085 SP |
201 | if (number_of_loops () <= 1 |
202 | /* FIXME: This limit on the number of basic blocks of a function | |
203 | should be removed when the SCOP detection is faster. */ | |
b6bb0094 | 204 | || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)) |
f8bf9252 | 205 | { |
204b560f SP |
206 | if (dump_file && (dump_flags & TDF_DETAILS)) |
207 | print_global_statistics (dump_file); | |
f8bf9252 | 208 | |
33ad93b9 | 209 | isl_ctx_free (ctx); |
204b560f | 210 | return false; |
f8bf9252 SP |
211 | } |
212 | ||
cdb9802c | 213 | scev_reset (); |
204b560f SP |
214 | recompute_all_dominators (); |
215 | initialize_original_copy_tables (); | |
85437633 | 216 | |
33ad93b9 | 217 | cloog_state = cloog_isl_state_malloc (ctx); |
f8bf9252 | 218 | |
204b560f SP |
219 | if (dump_file && dump_flags) |
220 | dump_function_to_file (current_function_decl, dump_file, dump_flags); | |
f8bf9252 | 221 | |
204b560f | 222 | return true; |
f8bf9252 SP |
223 | } |
224 | ||
204b560f SP |
225 | /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is |
226 | true. */ | |
f8bf9252 SP |
227 | |
228 | static void | |
204b560f | 229 | graphite_finalize (bool need_cfg_cleanup_p) |
f8bf9252 | 230 | { |
204b560f | 231 | if (need_cfg_cleanup_p) |
8e88f9fd | 232 | { |
fd4a56ff | 233 | scev_reset (); |
8e88f9fd SP |
234 | cleanup_tree_cfg (); |
235 | profile_status = PROFILE_ABSENT; | |
236 | release_recorded_exits (); | |
237 | tree_estimate_probability (); | |
238 | } | |
f8bf9252 | 239 | |
57d598f7 | 240 | cloog_state_free (cloog_state); |
204b560f | 241 | free_original_copy_tables (); |
a61e3d2a | 242 | |
204b560f SP |
243 | if (dump_file && dump_flags) |
244 | print_loops (dump_file, 3); | |
f8bf9252 SP |
245 | } |
246 | ||
33ad93b9 RG |
247 | isl_ctx *the_isl_ctx; |
248 | ||
f8bf9252 SP |
249 | /* Perform a set of linear transforms on the loops of the current |
250 | function. */ | |
251 | ||
252 | void | |
253 | graphite_transform_loops (void) | |
254 | { | |
255 | int i; | |
256 | scop_p scop; | |
204b560f SP |
257 | bool need_cfg_cleanup_p = false; |
258 | VEC (scop_p, heap) *scops = NULL; | |
259 | htab_t bb_pbb_mapping; | |
33ad93b9 | 260 | isl_ctx *ctx; |
f8bf9252 | 261 | |
62e0a1ed RG |
262 | /* If a function is parallel it was most probably already run through graphite |
263 | once. No need to run again. */ | |
264 | if (parallelized_function_p (cfun->decl)) | |
265 | return; | |
266 | ||
33ad93b9 RG |
267 | ctx = isl_ctx_alloc (); |
268 | isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT); | |
269 | if (!graphite_initialize (ctx)) | |
f8bf9252 SP |
270 | return; |
271 | ||
33ad93b9 | 272 | the_isl_ctx = ctx; |
204b560f | 273 | build_scops (&scops); |
f8bf9252 SP |
274 | |
275 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
f8bf9252 | 276 | { |
204b560f SP |
277 | print_graphite_statistics (dump_file, scops); |
278 | print_global_statistics (dump_file); | |
279 | } | |
0b040072 | 280 | |
204b560f | 281 | bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free); |
3a7086cc | 282 | |
ac47786e | 283 | FOR_EACH_VEC_ELT (scop_p, scops, i, scop) |
6a7441f5 SP |
284 | if (dbg_cnt (graphite_scop)) |
285 | { | |
33ad93b9 | 286 | scop->ctx = ctx; |
efa21390 | 287 | build_poly_scop (scop); |
f8bf9252 | 288 | |
efa21390 SP |
289 | if (POLY_SCOP_P (scop) |
290 | && apply_poly_transforms (scop) | |
291 | && gloog (scop, bb_pbb_mapping)) | |
292 | need_cfg_cleanup_p = true; | |
293 | } | |
f8bf9252 | 294 | |
204b560f SP |
295 | htab_delete (bb_pbb_mapping); |
296 | free_scops (scops); | |
297 | graphite_finalize (need_cfg_cleanup_p); | |
33ad93b9 RG |
298 | the_isl_ctx = NULL; |
299 | isl_ctx_free (ctx); | |
f8bf9252 SP |
300 | } |
301 | ||
302 | #else /* If Cloog is not available: #ifndef HAVE_cloog. */ | |
303 | ||
304 | void | |
305 | graphite_transform_loops (void) | |
306 | { | |
f8bf9252 SP |
307 | sorry ("Graphite loop optimizations cannot be used"); |
308 | } | |
309 | ||
310 | #endif |