]>
Commit | Line | Data |
---|---|---|
f8bf9252 | 1 | /* Gimple Represented as Polyhedra. |
96867bbd | 2 | Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc. |
f8bf9252 SP |
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 | |
204b560f | 23 | to GIMPLE. |
f8bf9252 SP |
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 | |
204b560f | 28 | the related work. |
f8bf9252 SP |
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" | |
45 | #include "toplev.h" | |
46 | #include "tree-dump.h" | |
47 | #include "timevar.h" | |
48 | #include "cfgloop.h" | |
49 | #include "tree-chrec.h" | |
50 | #include "tree-data-ref.h" | |
51 | #include "tree-scalar-evolution.h" | |
52 | #include "tree-pass.h" | |
81b822d5 | 53 | #include "value-prof.h" |
f8bf9252 SP |
54 | #include "pointer-set.h" |
55 | #include "gimple.h" | |
204b560f | 56 | #include "sese.h" |
f8bf9252 SP |
57 | |
58 | #ifdef HAVE_cloog | |
bcbe3b25 SP |
59 | |
60 | /* The CLooG header file is not -Wc++-compat ready as of 2009-05-11. | |
61 | This #pragma should be removed when it is ready. */ | |
62 | #if GCC_VERSION >= 4003 | |
63 | #pragma GCC diagnostic warning "-Wc++-compat" | |
64 | #endif | |
65 | ||
f8bf9252 | 66 | #include "cloog/cloog.h" |
204b560f SP |
67 | #include "ppl_c.h" |
68 | #include "graphite-ppl.h" | |
f8bf9252 | 69 | #include "graphite.h" |
204b560f SP |
70 | #include "graphite-poly.h" |
71 | #include "graphite-scop-detection.h" | |
72 | #include "graphite-clast-to-gimple.h" | |
73 | #include "graphite-sese-to-poly.h" | |
f8bf9252 | 74 | |
204b560f | 75 | /* Print global statistics to FILE. */ |
4d6c7237 SP |
76 | |
77 | static void | |
204b560f | 78 | print_global_statistics (FILE* file) |
4d6c7237 | 79 | { |
204b560f SP |
80 | long n_bbs = 0; |
81 | long n_loops = 0; | |
82 | long n_stmts = 0; | |
83 | long n_conditions = 0; | |
84 | long n_p_bbs = 0; | |
85 | long n_p_loops = 0; | |
86 | long n_p_stmts = 0; | |
87 | long n_p_conditions = 0; | |
4d6c7237 | 88 | |
204b560f | 89 | basic_block bb; |
4d6c7237 | 90 | |
204b560f SP |
91 | FOR_ALL_BB (bb) |
92 | { | |
93 | gimple_stmt_iterator psi; | |
4d6c7237 | 94 | |
204b560f SP |
95 | n_bbs++; |
96 | n_p_bbs += bb->count; | |
4d6c7237 | 97 | |
204b560f SP |
98 | /* Ignore artificial surrounding loop. */ |
99 | if (bb == bb->loop_father->header | |
100 | && bb->index != 0) | |
4d6c7237 | 101 | { |
204b560f SP |
102 | n_loops++; |
103 | n_p_loops += bb->count; | |
4d6c7237 | 104 | } |
4d6c7237 | 105 | |
204b560f SP |
106 | if (VEC_length (edge, bb->succs) > 1) |
107 | { | |
108 | n_conditions++; | |
109 | n_p_conditions += bb->count; | |
110 | } | |
4d6c7237 | 111 | |
204b560f SP |
112 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
113 | { | |
114 | n_stmts++; | |
115 | n_p_stmts += bb->count; | |
116 | } | |
4d6c7237 SP |
117 | } |
118 | ||
204b560f SP |
119 | fprintf (file, "\nGlobal statistics ("); |
120 | fprintf (file, "BBS:%ld, ", n_bbs); | |
121 | fprintf (file, "LOOPS:%ld, ", n_loops); | |
122 | fprintf (file, "CONDITIONS:%ld, ", n_conditions); | |
123 | fprintf (file, "STMTS:%ld)\n", n_stmts); | |
124 | fprintf (file, "\nGlobal profiling statistics ("); | |
125 | fprintf (file, "BBS:%ld, ", n_p_bbs); | |
126 | fprintf (file, "LOOPS:%ld, ", n_p_loops); | |
127 | fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); | |
128 | fprintf (file, "STMTS:%ld)\n", n_p_stmts); | |
f8bf9252 SP |
129 | } |
130 | ||
204b560f | 131 | /* Print statistics for SCOP to FILE. */ |
f8bf9252 SP |
132 | |
133 | static void | |
204b560f | 134 | print_graphite_scop_statistics (FILE* file, scop_p scop) |
f8bf9252 | 135 | { |
204b560f SP |
136 | long n_bbs = 0; |
137 | long n_loops = 0; | |
138 | long n_stmts = 0; | |
139 | long n_conditions = 0; | |
140 | long n_p_bbs = 0; | |
141 | long n_p_loops = 0; | |
142 | long n_p_stmts = 0; | |
143 | long n_p_conditions = 0; | |
f8bf9252 | 144 | |
204b560f | 145 | basic_block bb; |
f8bf9252 | 146 | |
204b560f | 147 | FOR_ALL_BB (bb) |
f8bf9252 | 148 | { |
204b560f SP |
149 | gimple_stmt_iterator psi; |
150 | loop_p loop = bb->loop_father; | |
f8bf9252 | 151 | |
204b560f SP |
152 | if (!bb_in_sese_p (bb, SCOP_REGION (scop))) |
153 | continue; | |
f8bf9252 | 154 | |
204b560f SP |
155 | n_bbs++; |
156 | n_p_bbs += bb->count; | |
f8bf9252 | 157 | |
204b560f | 158 | if (VEC_length (edge, bb->succs) > 1) |
f8bf9252 | 159 | { |
204b560f SP |
160 | n_conditions++; |
161 | n_p_conditions += bb->count; | |
f8bf9252 | 162 | } |
f8bf9252 | 163 | |
204b560f | 164 | for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
f8bf9252 | 165 | { |
204b560f SP |
166 | n_stmts++; |
167 | n_p_stmts += bb->count; | |
f8bf9252 | 168 | } |
f8bf9252 | 169 | |
204b560f SP |
170 | if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) |
171 | { | |
172 | n_loops++; | |
173 | n_p_loops += bb->count; | |
174 | } | |
175 | } | |
6a114766 | 176 | |
204b560f SP |
177 | fprintf (file, "\nSCoP statistics ("); |
178 | fprintf (file, "BBS:%ld, ", n_bbs); | |
179 | fprintf (file, "LOOPS:%ld, ", n_loops); | |
180 | fprintf (file, "CONDITIONS:%ld, ", n_conditions); | |
181 | fprintf (file, "STMTS:%ld)\n", n_stmts); | |
182 | fprintf (file, "\nSCoP profiling statistics ("); | |
183 | fprintf (file, "BBS:%ld, ", n_p_bbs); | |
184 | fprintf (file, "LOOPS:%ld, ", n_p_loops); | |
185 | fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); | |
186 | fprintf (file, "STMTS:%ld)\n", n_p_stmts); | |
f8bf9252 SP |
187 | } |
188 | ||
204b560f | 189 | /* Print statistics for SCOPS to FILE. */ |
f8bf9252 | 190 | |
204b560f SP |
191 | static void |
192 | print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops) | |
f8bf9252 | 193 | { |
f8bf9252 | 194 | int i; |
f8bf9252 | 195 | |
204b560f | 196 | scop_p scop; |
f8bf9252 | 197 | |
204b560f SP |
198 | for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) |
199 | print_graphite_scop_statistics (file, scop); | |
f8bf9252 SP |
200 | } |
201 | ||
204b560f | 202 | /* Initialize graphite: when there are no loops returns false. */ |
f8bf9252 SP |
203 | |
204 | static bool | |
204b560f | 205 | graphite_initialize (void) |
f8bf9252 | 206 | { |
204b560f | 207 | if (number_of_loops () <= 1) |
f8bf9252 | 208 | { |
204b560f SP |
209 | if (dump_file && (dump_flags & TDF_DETAILS)) |
210 | print_global_statistics (dump_file); | |
f8bf9252 | 211 | |
204b560f | 212 | return false; |
f8bf9252 SP |
213 | } |
214 | ||
204b560f SP |
215 | recompute_all_dominators (); |
216 | initialize_original_copy_tables (); | |
217 | cloog_initialize (); | |
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 SP |
231 | if (need_cfg_cleanup_p) |
232 | cleanup_tree_cfg (); | |
f8bf9252 | 233 | |
204b560f SP |
234 | cloog_finalize (); |
235 | free_original_copy_tables (); | |
236 | free_aux_in_new_loops (); | |
a61e3d2a | 237 | |
204b560f SP |
238 | if (dump_file && dump_flags) |
239 | print_loops (dump_file, 3); | |
f8bf9252 SP |
240 | } |
241 | ||
242 | /* Perform a set of linear transforms on the loops of the current | |
243 | function. */ | |
244 | ||
245 | void | |
246 | graphite_transform_loops (void) | |
247 | { | |
248 | int i; | |
249 | scop_p scop; | |
204b560f SP |
250 | bool need_cfg_cleanup_p = false; |
251 | VEC (scop_p, heap) *scops = NULL; | |
252 | htab_t bb_pbb_mapping; | |
f8bf9252 | 253 | |
204b560f | 254 | if (!graphite_initialize ()) |
f8bf9252 SP |
255 | return; |
256 | ||
204b560f | 257 | build_scops (&scops); |
f8bf9252 SP |
258 | |
259 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
f8bf9252 | 260 | { |
204b560f SP |
261 | print_graphite_statistics (dump_file, scops); |
262 | print_global_statistics (dump_file); | |
263 | } | |
0b040072 | 264 | |
204b560f | 265 | bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free); |
f8bf9252 | 266 | |
204b560f SP |
267 | for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) |
268 | { | |
269 | bool transform_done = false; | |
f8bf9252 | 270 | |
204b560f | 271 | if (!build_poly_scop (scop)) |
f8bf9252 SP |
272 | continue; |
273 | ||
204b560f SP |
274 | if (apply_poly_transforms (scop)) |
275 | transform_done = gloog (scop, bb_pbb_mapping); | |
c34a77fd | 276 | else |
204b560f SP |
277 | check_poly_representation (scop); |
278 | ||
279 | if (transform_done) | |
c34a77fd | 280 | { |
204b560f SP |
281 | scev_reset (); |
282 | need_cfg_cleanup_p = true; | |
c34a77fd | 283 | } |
f8bf9252 SP |
284 | } |
285 | ||
3cf0e270 | 286 | if (flag_loop_parallelize_all) |
204b560f | 287 | mark_loops_parallel (bb_pbb_mapping); |
b840fb02 | 288 | |
204b560f SP |
289 | htab_delete (bb_pbb_mapping); |
290 | free_scops (scops); | |
291 | graphite_finalize (need_cfg_cleanup_p); | |
f8bf9252 SP |
292 | } |
293 | ||
294 | #else /* If Cloog is not available: #ifndef HAVE_cloog. */ | |
295 | ||
296 | void | |
297 | graphite_transform_loops (void) | |
298 | { | |
f8bf9252 SP |
299 | sorry ("Graphite loop optimizations cannot be used"); |
300 | } | |
301 | ||
302 | #endif |