]>
Commit | Line | Data |
---|---|---|
255b6be7 | 1 | /* Gimple Represented as Polyhedra. |
711789cc | 2 | Copyright (C) 2006-2013 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" | |
87e20041 | 36 | |
37 | #ifdef HAVE_cloog | |
38 | #include <isl/set.h> | |
39 | #include <isl/map.h> | |
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> | |
45 | #endif | |
46 | ||
255b6be7 | 47 | #include "system.h" |
48 | #include "coretypes.h" | |
52f91c04 | 49 | #include "diagnostic-core.h" |
69ee5dbb | 50 | #include "tree-ssa.h" |
255b6be7 | 51 | #include "tree-dump.h" |
255b6be7 | 52 | #include "cfgloop.h" |
53 | #include "tree-chrec.h" | |
54 | #include "tree-data-ref.h" | |
55 | #include "tree-scalar-evolution.h" | |
26c166eb | 56 | #include "sese.h" |
e819c864 | 57 | #include "dbgcnt.h" |
64641360 | 58 | #include "tree-parloops.h" |
59 | #include "tree-pass.h" | |
424a4a92 | 60 | #include "tree-cfgcleanup.h" |
255b6be7 | 61 | |
62 | #ifdef HAVE_cloog | |
d970c7fe | 63 | |
26c166eb | 64 | #include "graphite-poly.h" |
65 | #include "graphite-scop-detection.h" | |
66 | #include "graphite-clast-to-gimple.h" | |
67 | #include "graphite-sese-to-poly.h" | |
d9dd21a8 | 68 | #include "graphite-htab.h" |
255b6be7 | 69 | |
98b9957e | 70 | CloogState *cloog_state; |
71 | ||
26c166eb | 72 | /* Print global statistics to FILE. */ |
7d3f5847 | 73 | |
74 | static void | |
26c166eb | 75 | print_global_statistics (FILE* file) |
7d3f5847 | 76 | { |
26c166eb | 77 | long n_bbs = 0; |
78 | long n_loops = 0; | |
79 | long n_stmts = 0; | |
80 | long n_conditions = 0; | |
81 | long n_p_bbs = 0; | |
82 | long n_p_loops = 0; | |
83 | long n_p_stmts = 0; | |
84 | long n_p_conditions = 0; | |
7d3f5847 | 85 | |
26c166eb | 86 | basic_block bb; |
7d3f5847 | 87 | |
26c166eb | 88 | FOR_ALL_BB (bb) |
89 | { | |
90 | gimple_stmt_iterator psi; | |
7d3f5847 | 91 | |
26c166eb | 92 | n_bbs++; |
93 | n_p_bbs += bb->count; | |
7d3f5847 | 94 | |
26c166eb | 95 | /* Ignore artificial surrounding loop. */ |
96 | if (bb == bb->loop_father->header | |
97 | && bb->index != 0) | |
7d3f5847 | 98 | { |
26c166eb | 99 | n_loops++; |
100 | n_p_loops += bb->count; | |
7d3f5847 | 101 | } |
7d3f5847 | 102 | |
7bf60644 | 103 | if (EDGE_COUNT (bb->succs) > 1) |
26c166eb | 104 | { |
105 | n_conditions++; | |
106 | n_p_conditions += bb->count; | |
107 | } | |
7d3f5847 | 108 | |
26c166eb | 109 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
110 | { | |
111 | n_stmts++; | |
112 | n_p_stmts += bb->count; | |
113 | } | |
7d3f5847 | 114 | } |
115 | ||
26c166eb | 116 | fprintf (file, "\nGlobal statistics ("); |
117 | fprintf (file, "BBS:%ld, ", n_bbs); | |
118 | fprintf (file, "LOOPS:%ld, ", n_loops); | |
119 | fprintf (file, "CONDITIONS:%ld, ", n_conditions); | |
120 | fprintf (file, "STMTS:%ld)\n", n_stmts); | |
121 | fprintf (file, "\nGlobal profiling statistics ("); | |
122 | fprintf (file, "BBS:%ld, ", n_p_bbs); | |
123 | fprintf (file, "LOOPS:%ld, ", n_p_loops); | |
124 | fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); | |
125 | fprintf (file, "STMTS:%ld)\n", n_p_stmts); | |
255b6be7 | 126 | } |
127 | ||
26c166eb | 128 | /* Print statistics for SCOP to FILE. */ |
255b6be7 | 129 | |
130 | static void | |
26c166eb | 131 | print_graphite_scop_statistics (FILE* file, scop_p scop) |
255b6be7 | 132 | { |
26c166eb | 133 | long n_bbs = 0; |
134 | long n_loops = 0; | |
135 | long n_stmts = 0; | |
136 | long n_conditions = 0; | |
137 | long n_p_bbs = 0; | |
138 | long n_p_loops = 0; | |
139 | long n_p_stmts = 0; | |
140 | long n_p_conditions = 0; | |
255b6be7 | 141 | |
26c166eb | 142 | basic_block bb; |
255b6be7 | 143 | |
26c166eb | 144 | FOR_ALL_BB (bb) |
255b6be7 | 145 | { |
26c166eb | 146 | gimple_stmt_iterator psi; |
147 | loop_p loop = bb->loop_father; | |
255b6be7 | 148 | |
26c166eb | 149 | if (!bb_in_sese_p (bb, SCOP_REGION (scop))) |
150 | continue; | |
255b6be7 | 151 | |
26c166eb | 152 | n_bbs++; |
153 | n_p_bbs += bb->count; | |
255b6be7 | 154 | |
7bf60644 | 155 | if (EDGE_COUNT (bb->succs) > 1) |
255b6be7 | 156 | { |
26c166eb | 157 | n_conditions++; |
158 | n_p_conditions += bb->count; | |
255b6be7 | 159 | } |
255b6be7 | 160 | |
26c166eb | 161 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
255b6be7 | 162 | { |
26c166eb | 163 | n_stmts++; |
164 | n_p_stmts += bb->count; | |
255b6be7 | 165 | } |
255b6be7 | 166 | |
26c166eb | 167 | if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) |
168 | { | |
169 | n_loops++; | |
170 | n_p_loops += bb->count; | |
171 | } | |
172 | } | |
145bdf6a | 173 | |
26c166eb | 174 | fprintf (file, "\nSCoP statistics ("); |
175 | fprintf (file, "BBS:%ld, ", n_bbs); | |
176 | fprintf (file, "LOOPS:%ld, ", n_loops); | |
177 | fprintf (file, "CONDITIONS:%ld, ", n_conditions); | |
178 | fprintf (file, "STMTS:%ld)\n", n_stmts); | |
179 | fprintf (file, "\nSCoP profiling statistics ("); | |
180 | fprintf (file, "BBS:%ld, ", n_p_bbs); | |
181 | fprintf (file, "LOOPS:%ld, ", n_p_loops); | |
182 | fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); | |
183 | fprintf (file, "STMTS:%ld)\n", n_p_stmts); | |
255b6be7 | 184 | } |
185 | ||
26c166eb | 186 | /* Print statistics for SCOPS to FILE. */ |
255b6be7 | 187 | |
26c166eb | 188 | static void |
f1f41a6c | 189 | print_graphite_statistics (FILE* file, vec<scop_p> scops) |
255b6be7 | 190 | { |
255b6be7 | 191 | int i; |
255b6be7 | 192 | |
26c166eb | 193 | scop_p scop; |
255b6be7 | 194 | |
f1f41a6c | 195 | FOR_EACH_VEC_ELT (scops, i, scop) |
26c166eb | 196 | print_graphite_scop_statistics (file, scop); |
255b6be7 | 197 | } |
198 | ||
26c166eb | 199 | /* Initialize graphite: when there are no loops returns false. */ |
255b6be7 | 200 | |
201 | static bool | |
87e20041 | 202 | graphite_initialize (isl_ctx *ctx) |
255b6be7 | 203 | { |
41f75a99 | 204 | if (number_of_loops (cfun) <= 1 |
ef98ee10 | 205 | /* FIXME: This limit on the number of basic blocks of a function |
206 | should be removed when the SCOP detection is faster. */ | |
94ba21de | 207 | || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)) |
255b6be7 | 208 | { |
26c166eb | 209 | if (dump_file && (dump_flags & TDF_DETAILS)) |
210 | print_global_statistics (dump_file); | |
255b6be7 | 211 | |
87e20041 | 212 | isl_ctx_free (ctx); |
26c166eb | 213 | return false; |
255b6be7 | 214 | } |
215 | ||
d4d6f501 | 216 | scev_reset (); |
26c166eb | 217 | recompute_all_dominators (); |
218 | initialize_original_copy_tables (); | |
f0fc00f2 | 219 | |
87e20041 | 220 | cloog_state = cloog_isl_state_malloc (ctx); |
255b6be7 | 221 | |
26c166eb | 222 | if (dump_file && dump_flags) |
223 | dump_function_to_file (current_function_decl, dump_file, dump_flags); | |
255b6be7 | 224 | |
26c166eb | 225 | return true; |
255b6be7 | 226 | } |
227 | ||
26c166eb | 228 | /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is |
229 | true. */ | |
255b6be7 | 230 | |
231 | static void | |
26c166eb | 232 | graphite_finalize (bool need_cfg_cleanup_p) |
255b6be7 | 233 | { |
26c166eb | 234 | if (need_cfg_cleanup_p) |
675d86b2 | 235 | { |
d9458edc | 236 | scev_reset (); |
675d86b2 | 237 | cleanup_tree_cfg (); |
238 | profile_status = PROFILE_ABSENT; | |
239 | release_recorded_exits (); | |
240 | tree_estimate_probability (); | |
241 | } | |
255b6be7 | 242 | |
98b9957e | 243 | cloog_state_free (cloog_state); |
26c166eb | 244 | free_original_copy_tables (); |
d0483ac6 | 245 | |
26c166eb | 246 | if (dump_file && dump_flags) |
247 | print_loops (dump_file, 3); | |
255b6be7 | 248 | } |
249 | ||
87e20041 | 250 | isl_ctx *the_isl_ctx; |
251 | ||
255b6be7 | 252 | /* Perform a set of linear transforms on the loops of the current |
253 | function. */ | |
254 | ||
255 | void | |
256 | graphite_transform_loops (void) | |
257 | { | |
258 | int i; | |
259 | scop_p scop; | |
26c166eb | 260 | bool need_cfg_cleanup_p = false; |
1e094109 | 261 | vec<scop_p> scops = vNULL; |
d9dd21a8 | 262 | bb_pbb_htab_type bb_pbb_mapping; |
87e20041 | 263 | isl_ctx *ctx; |
255b6be7 | 264 | |
479a6d79 | 265 | /* If a function is parallel it was most probably already run through graphite |
266 | once. No need to run again. */ | |
267 | if (parallelized_function_p (cfun->decl)) | |
268 | return; | |
269 | ||
87e20041 | 270 | ctx = isl_ctx_alloc (); |
9af5ce0c | 271 | isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); |
87e20041 | 272 | if (!graphite_initialize (ctx)) |
255b6be7 | 273 | return; |
274 | ||
87e20041 | 275 | the_isl_ctx = ctx; |
26c166eb | 276 | build_scops (&scops); |
255b6be7 | 277 | |
278 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
255b6be7 | 279 | { |
26c166eb | 280 | print_graphite_statistics (dump_file, scops); |
281 | print_global_statistics (dump_file); | |
282 | } | |
35fb1eb0 | 283 | |
d9dd21a8 | 284 | bb_pbb_mapping.create (10); |
5d2603f9 | 285 | |
f1f41a6c | 286 | FOR_EACH_VEC_ELT (scops, i, scop) |
e819c864 | 287 | if (dbg_cnt (graphite_scop)) |
288 | { | |
87e20041 | 289 | scop->ctx = ctx; |
8c6b3774 | 290 | build_poly_scop (scop); |
255b6be7 | 291 | |
8c6b3774 | 292 | if (POLY_SCOP_P (scop) |
293 | && apply_poly_transforms (scop) | |
294 | && gloog (scop, bb_pbb_mapping)) | |
295 | need_cfg_cleanup_p = true; | |
296 | } | |
255b6be7 | 297 | |
d9dd21a8 | 298 | bb_pbb_mapping.dispose (); |
26c166eb | 299 | free_scops (scops); |
300 | graphite_finalize (need_cfg_cleanup_p); | |
87e20041 | 301 | the_isl_ctx = NULL; |
302 | isl_ctx_free (ctx); | |
255b6be7 | 303 | } |
304 | ||
305 | #else /* If Cloog is not available: #ifndef HAVE_cloog. */ | |
306 | ||
64641360 | 307 | static void |
255b6be7 | 308 | graphite_transform_loops (void) |
309 | { | |
255b6be7 | 310 | sorry ("Graphite loop optimizations cannot be used"); |
311 | } | |
312 | ||
313 | #endif | |
64641360 | 314 | |
315 | ||
316 | static unsigned int | |
317 | graphite_transforms (void) | |
318 | { | |
319 | if (!current_loops) | |
320 | return 0; | |
321 | ||
322 | graphite_transform_loops (); | |
323 | ||
324 | return 0; | |
325 | } | |
326 | ||
327 | static bool | |
328 | gate_graphite_transforms (void) | |
329 | { | |
330 | /* Enable -fgraphite pass if any one of the graphite optimization flags | |
331 | is turned on. */ | |
332 | if (flag_loop_block | |
333 | || flag_loop_interchange | |
334 | || flag_loop_strip_mine | |
335 | || flag_graphite_identity | |
336 | || flag_loop_parallelize_all | |
337 | || flag_loop_optimize_isl) | |
338 | flag_graphite = 1; | |
339 | ||
340 | return flag_graphite != 0; | |
341 | } | |
342 | ||
343 | namespace { | |
344 | ||
345 | const pass_data pass_data_graphite = | |
346 | { | |
347 | GIMPLE_PASS, /* type */ | |
348 | "graphite0", /* name */ | |
349 | OPTGROUP_LOOP, /* optinfo_flags */ | |
350 | true, /* has_gate */ | |
351 | false, /* has_execute */ | |
352 | TV_GRAPHITE, /* tv_id */ | |
353 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
354 | 0, /* properties_provided */ | |
355 | 0, /* properties_destroyed */ | |
356 | 0, /* todo_flags_start */ | |
357 | 0, /* todo_flags_finish */ | |
358 | }; | |
359 | ||
360 | class pass_graphite : public gimple_opt_pass | |
361 | { | |
362 | public: | |
363 | pass_graphite (gcc::context *ctxt) | |
364 | : gimple_opt_pass (pass_data_graphite, ctxt) | |
365 | {} | |
366 | ||
367 | /* opt_pass methods: */ | |
368 | bool gate () { return gate_graphite_transforms (); } | |
369 | ||
370 | }; // class pass_graphite | |
371 | ||
372 | } // anon namespace | |
373 | ||
374 | gimple_opt_pass * | |
375 | make_pass_graphite (gcc::context *ctxt) | |
376 | { | |
377 | return new pass_graphite (ctxt); | |
378 | } | |
379 | ||
380 | namespace { | |
381 | ||
382 | const pass_data pass_data_graphite_transforms = | |
383 | { | |
384 | GIMPLE_PASS, /* type */ | |
385 | "graphite", /* name */ | |
386 | OPTGROUP_LOOP, /* optinfo_flags */ | |
387 | true, /* has_gate */ | |
388 | true, /* has_execute */ | |
389 | TV_GRAPHITE_TRANSFORMS, /* tv_id */ | |
390 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
391 | 0, /* properties_provided */ | |
392 | 0, /* properties_destroyed */ | |
393 | 0, /* todo_flags_start */ | |
394 | 0, /* todo_flags_finish */ | |
395 | }; | |
396 | ||
397 | class pass_graphite_transforms : public gimple_opt_pass | |
398 | { | |
399 | public: | |
400 | pass_graphite_transforms (gcc::context *ctxt) | |
401 | : gimple_opt_pass (pass_data_graphite_transforms, ctxt) | |
402 | {} | |
403 | ||
404 | /* opt_pass methods: */ | |
405 | bool gate () { return gate_graphite_transforms (); } | |
406 | unsigned int execute () { return graphite_transforms (); } | |
407 | ||
408 | }; // class pass_graphite_transforms | |
409 | ||
410 | } // anon namespace | |
411 | ||
412 | gimple_opt_pass * | |
413 | make_pass_graphite_transforms (gcc::context *ctxt) | |
414 | { | |
415 | return new pass_graphite_transforms (ctxt); | |
416 | } | |
417 | ||
418 |