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