* config/i386/i386.h (TARGET_SUPPORTS_WIDE_INT): New define.
[official-gcc.git] / gcc / graphite.c
blobc8f0617a5fb86de8789ef0f85bef5b8250652596
1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
5 This file is part of GCC.
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.
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.
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/>. */
21 /* This pass converts GIMPLE to GRAPHITE, performs some loop
22 transformations and then converts the resulting representation back
23 to GIMPLE.
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.
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. */
35 #include "config.h"
37 #ifdef HAVE_isl
38 #include <isl/set.h>
39 #include <isl/map.h>
40 #include <isl/options.h>
41 #include <isl/union_map.h>
42 #endif
44 #include "system.h"
45 #include "coretypes.h"
46 #include "diagnostic-core.h"
47 #include "hash-set.h"
48 #include "machmode.h"
49 #include "vec.h"
50 #include "double-int.h"
51 #include "input.h"
52 #include "alias.h"
53 #include "symtab.h"
54 #include "options.h"
55 #include "wide-int.h"
56 #include "inchash.h"
57 #include "tree.h"
58 #include "fold-const.h"
59 #include "predict.h"
60 #include "tm.h"
61 #include "hard-reg-set.h"
62 #include "input.h"
63 #include "function.h"
64 #include "dominance.h"
65 #include "cfg.h"
66 #include "basic-block.h"
67 #include "tree-ssa-alias.h"
68 #include "internal-fn.h"
69 #include "gimple-expr.h"
70 #include "is-a.h"
71 #include "gimple.h"
72 #include "gimple-iterator.h"
73 #include "tree-cfg.h"
74 #include "tree-ssa-loop.h"
75 #include "tree-dump.h"
76 #include "cfgloop.h"
77 #include "tree-chrec.h"
78 #include "tree-data-ref.h"
79 #include "tree-scalar-evolution.h"
80 #include "sese.h"
81 #include "dbgcnt.h"
82 #include "tree-parloops.h"
83 #include "tree-pass.h"
84 #include "tree-cfgcleanup.h"
86 #ifdef HAVE_isl
88 #include "graphite-poly.h"
89 #include "graphite-scop-detection.h"
90 #include "graphite-isl-ast-to-gimple.h"
91 #include "graphite-sese-to-poly.h"
93 /* Print global statistics to FILE. */
95 static void
96 print_global_statistics (FILE* file)
98 long n_bbs = 0;
99 long n_loops = 0;
100 long n_stmts = 0;
101 long n_conditions = 0;
102 long n_p_bbs = 0;
103 long n_p_loops = 0;
104 long n_p_stmts = 0;
105 long n_p_conditions = 0;
107 basic_block bb;
109 FOR_ALL_BB_FN (bb, cfun)
111 gimple_stmt_iterator psi;
113 n_bbs++;
114 n_p_bbs += bb->count;
116 /* Ignore artificial surrounding loop. */
117 if (bb == bb->loop_father->header
118 && bb->index != 0)
120 n_loops++;
121 n_p_loops += bb->count;
124 if (EDGE_COUNT (bb->succs) > 1)
126 n_conditions++;
127 n_p_conditions += bb->count;
130 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
132 n_stmts++;
133 n_p_stmts += bb->count;
137 fprintf (file, "\nGlobal statistics (");
138 fprintf (file, "BBS:%ld, ", n_bbs);
139 fprintf (file, "LOOPS:%ld, ", n_loops);
140 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
141 fprintf (file, "STMTS:%ld)\n", n_stmts);
142 fprintf (file, "\nGlobal profiling statistics (");
143 fprintf (file, "BBS:%ld, ", n_p_bbs);
144 fprintf (file, "LOOPS:%ld, ", n_p_loops);
145 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
146 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
149 /* Print statistics for SCOP to FILE. */
151 static void
152 print_graphite_scop_statistics (FILE* file, scop_p scop)
154 long n_bbs = 0;
155 long n_loops = 0;
156 long n_stmts = 0;
157 long n_conditions = 0;
158 long n_p_bbs = 0;
159 long n_p_loops = 0;
160 long n_p_stmts = 0;
161 long n_p_conditions = 0;
163 basic_block bb;
165 FOR_ALL_BB_FN (bb, cfun)
167 gimple_stmt_iterator psi;
168 loop_p loop = bb->loop_father;
170 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
171 continue;
173 n_bbs++;
174 n_p_bbs += bb->count;
176 if (EDGE_COUNT (bb->succs) > 1)
178 n_conditions++;
179 n_p_conditions += bb->count;
182 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
184 n_stmts++;
185 n_p_stmts += bb->count;
188 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
190 n_loops++;
191 n_p_loops += bb->count;
195 fprintf (file, "\nSCoP statistics (");
196 fprintf (file, "BBS:%ld, ", n_bbs);
197 fprintf (file, "LOOPS:%ld, ", n_loops);
198 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
199 fprintf (file, "STMTS:%ld)\n", n_stmts);
200 fprintf (file, "\nSCoP profiling statistics (");
201 fprintf (file, "BBS:%ld, ", n_p_bbs);
202 fprintf (file, "LOOPS:%ld, ", n_p_loops);
203 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
204 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
207 /* Print statistics for SCOPS to FILE. */
209 static void
210 print_graphite_statistics (FILE* file, vec<scop_p> scops)
212 int i;
214 scop_p scop;
216 FOR_EACH_VEC_ELT (scops, i, scop)
217 print_graphite_scop_statistics (file, scop);
220 /* Initialize graphite: when there are no loops returns false. */
222 static bool
223 graphite_initialize (isl_ctx *ctx)
225 if (number_of_loops (cfun) <= 1
226 /* FIXME: This limit on the number of basic blocks of a function
227 should be removed when the SCOP detection is faster. */
228 || (n_basic_blocks_for_fn (cfun) >
229 PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)))
231 if (dump_file && (dump_flags & TDF_DETAILS))
232 print_global_statistics (dump_file);
234 isl_ctx_free (ctx);
235 return false;
238 scev_reset ();
239 recompute_all_dominators ();
240 initialize_original_copy_tables ();
242 if (dump_file && dump_flags)
243 dump_function_to_file (current_function_decl, dump_file, dump_flags);
245 return true;
248 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
249 true. */
251 static void
252 graphite_finalize (bool need_cfg_cleanup_p)
254 if (need_cfg_cleanup_p)
256 scev_reset ();
257 cleanup_tree_cfg ();
258 profile_status_for_fn (cfun) = PROFILE_ABSENT;
259 release_recorded_exits ();
260 tree_estimate_probability ();
263 free_original_copy_tables ();
265 if (dump_file && dump_flags)
266 print_loops (dump_file, 3);
269 isl_ctx *the_isl_ctx;
271 /* Perform a set of linear transforms on the loops of the current
272 function. */
274 void
275 graphite_transform_loops (void)
277 int i;
278 scop_p scop;
279 bool need_cfg_cleanup_p = false;
280 vec<scop_p> scops = vNULL;
281 isl_ctx *ctx;
283 /* If a function is parallel it was most probably already run through graphite
284 once. No need to run again. */
285 if (parallelized_function_p (cfun->decl))
286 return;
288 ctx = isl_ctx_alloc ();
289 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
290 if (!graphite_initialize (ctx))
291 return;
293 the_isl_ctx = ctx;
294 build_scops (&scops);
296 if (dump_file && (dump_flags & TDF_DETAILS))
298 print_graphite_statistics (dump_file, scops);
299 print_global_statistics (dump_file);
302 FOR_EACH_VEC_ELT (scops, i, scop)
303 if (dbg_cnt (graphite_scop))
305 scop->ctx = ctx;
306 build_poly_scop (scop);
308 if (POLY_SCOP_P (scop)
309 && apply_poly_transforms (scop)
310 && graphite_regenerate_ast_isl (scop))
311 need_cfg_cleanup_p = true;
315 free_scops (scops);
316 graphite_finalize (need_cfg_cleanup_p);
317 the_isl_ctx = NULL;
318 isl_ctx_free (ctx);
321 #else /* If ISL is not available: #ifndef HAVE_isl. */
323 static void
324 graphite_transform_loops (void)
326 sorry ("Graphite loop optimizations cannot be used (ISL is not available).");
329 #endif
332 static unsigned int
333 graphite_transforms (struct function *fun)
335 if (number_of_loops (fun) <= 1)
336 return 0;
338 graphite_transform_loops ();
340 return 0;
343 static bool
344 gate_graphite_transforms (void)
346 /* Enable -fgraphite pass if any one of the graphite optimization flags
347 is turned on. */
348 if (flag_loop_block
349 || flag_loop_interchange
350 || flag_loop_strip_mine
351 || flag_graphite_identity
352 || flag_loop_parallelize_all
353 || flag_loop_optimize_isl
354 || flag_loop_unroll_jam)
355 flag_graphite = 1;
357 return flag_graphite != 0;
360 namespace {
362 const pass_data pass_data_graphite =
364 GIMPLE_PASS, /* type */
365 "graphite0", /* name */
366 OPTGROUP_LOOP, /* optinfo_flags */
367 TV_GRAPHITE, /* tv_id */
368 ( PROP_cfg | PROP_ssa ), /* properties_required */
369 0, /* properties_provided */
370 0, /* properties_destroyed */
371 0, /* todo_flags_start */
372 0, /* todo_flags_finish */
375 class pass_graphite : public gimple_opt_pass
377 public:
378 pass_graphite (gcc::context *ctxt)
379 : gimple_opt_pass (pass_data_graphite, ctxt)
382 /* opt_pass methods: */
383 virtual bool gate (function *) { return gate_graphite_transforms (); }
385 }; // class pass_graphite
387 } // anon namespace
389 gimple_opt_pass *
390 make_pass_graphite (gcc::context *ctxt)
392 return new pass_graphite (ctxt);
395 namespace {
397 const pass_data pass_data_graphite_transforms =
399 GIMPLE_PASS, /* type */
400 "graphite", /* name */
401 OPTGROUP_LOOP, /* optinfo_flags */
402 TV_GRAPHITE_TRANSFORMS, /* tv_id */
403 ( PROP_cfg | PROP_ssa ), /* properties_required */
404 0, /* properties_provided */
405 0, /* properties_destroyed */
406 0, /* todo_flags_start */
407 0, /* todo_flags_finish */
410 class pass_graphite_transforms : public gimple_opt_pass
412 public:
413 pass_graphite_transforms (gcc::context *ctxt)
414 : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
417 /* opt_pass methods: */
418 virtual bool gate (function *) { return gate_graphite_transforms (); }
419 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
421 }; // class pass_graphite_transforms
423 } // anon namespace
425 gimple_opt_pass *
426 make_pass_graphite_transforms (gcc::context *ctxt)
428 return new pass_graphite_transforms (ctxt);