PR target/81369
[official-gcc.git] / gcc / graphite.c
blobaf336da5ad4489641dd507918688b757838f461f
1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2017 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 #define USES_ISL
32 #include "config.h"
33 #include "system.h"
34 #include "coretypes.h"
35 #include "backend.h"
36 #include "diagnostic-core.h"
37 #include "cfgloop.h"
38 #include "tree-pass.h"
39 #include "params.h"
40 #include "pretty-print.h"
42 #ifdef HAVE_isl
43 #include "cfghooks.h"
44 #include "tree.h"
45 #include "gimple.h"
46 #include "fold-const.h"
47 #include "gimple-iterator.h"
48 #include "tree-cfg.h"
49 #include "tree-ssa-loop.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
52 #include "dbgcnt.h"
53 #include "tree-parloops.h"
54 #include "tree-cfgcleanup.h"
55 #include "tree-vectorizer.h"
56 #include "graphite.h"
58 /* Print global statistics to FILE. */
60 static void
61 print_global_statistics (FILE* file)
63 long n_bbs = 0;
64 long n_loops = 0;
65 long n_stmts = 0;
66 long n_conditions = 0;
67 profile_count n_p_bbs = profile_count::zero ();
68 profile_count n_p_loops = profile_count::zero ();
69 profile_count n_p_stmts = profile_count::zero ();
70 profile_count n_p_conditions = profile_count::zero ();
72 basic_block bb;
74 FOR_ALL_BB_FN (bb, cfun)
76 gimple_stmt_iterator psi;
78 n_bbs++;
79 if (bb->count.initialized_p ())
80 n_p_bbs += bb->count;
82 /* Ignore artificial surrounding loop. */
83 if (bb == bb->loop_father->header
84 && bb->index != 0)
86 n_loops++;
87 n_p_loops += bb->count;
90 if (EDGE_COUNT (bb->succs) > 1)
92 n_conditions++;
93 if (bb->count.initialized_p ())
94 n_p_conditions += bb->count;
97 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
99 n_stmts++;
100 if (bb->count.initialized_p ())
101 n_p_stmts += bb->count;
105 fprintf (file, "\nGlobal statistics (");
106 fprintf (file, "BBS:%ld, ", n_bbs);
107 fprintf (file, "LOOPS:%ld, ", n_loops);
108 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
109 fprintf (file, "STMTS:%ld)\n", n_stmts);
110 fprintf (file, "\nGlobal profiling statistics (");
111 fprintf (file, "BBS:");
112 n_p_bbs.dump (file);
113 fprintf (file, ", LOOPS:");
114 n_p_loops.dump (file);
115 fprintf (file, ", CONDITIONS:");
116 n_p_conditions.dump (file);
117 fprintf (file, ", STMTS:");
118 n_p_stmts.dump (file);
119 fprintf (file, ")\n");
122 /* Print statistics for SCOP to FILE. */
124 static void
125 print_graphite_scop_statistics (FILE* file, scop_p scop)
127 long n_bbs = 0;
128 long n_loops = 0;
129 long n_stmts = 0;
130 long n_conditions = 0;
131 profile_count n_p_bbs = profile_count::zero ();
132 profile_count n_p_loops = profile_count::zero ();
133 profile_count n_p_stmts = profile_count::zero ();
134 profile_count n_p_conditions = profile_count::zero ();
136 basic_block bb;
138 FOR_ALL_BB_FN (bb, cfun)
140 gimple_stmt_iterator psi;
141 loop_p loop = bb->loop_father;
143 if (!bb_in_sese_p (bb, scop->scop_info->region))
144 continue;
146 n_bbs++;
147 if (bb->count.initialized_p ())
148 n_p_bbs += bb->count;
150 if (EDGE_COUNT (bb->succs) > 1)
152 n_conditions++;
153 n_p_conditions += bb->count;
156 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
158 n_stmts++;
159 n_p_stmts += bb->count;
162 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
164 n_loops++;
165 n_p_loops += bb->count;
169 fprintf (file, "\nFunction Name: %s\n", current_function_name ());
171 edge scop_begin = scop->scop_info->region.entry;
172 edge scop_end = scop->scop_info->region.exit;
174 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
175 scop_begin->src->index, scop_begin->dest->index);
176 fprintf (file, "exit_edge (bb_%d, bb_%d))",
177 scop_end->src->index, scop_end->dest->index);
179 fprintf (file, "\nSCoP statistics (");
180 fprintf (file, "BBS:%ld, ", n_bbs);
181 fprintf (file, "LOOPS:%ld, ", n_loops);
182 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
183 fprintf (file, "STMTS:%ld)\n", n_stmts);
184 fprintf (file, "\nSCoP profiling statistics (");
185 fprintf (file, "BBS:");
186 n_p_bbs.dump (file);
187 fprintf (file, ", LOOPS:");
188 n_p_loops.dump (file);
189 fprintf (file, ", CONDITIONS:");
190 n_p_conditions.dump (file);
191 fprintf (file, ", STMTS:");
192 n_p_stmts.dump (file);
193 fprintf (file, ")\n");
196 /* Print statistics for SCOPS to FILE. */
198 static void
199 print_graphite_statistics (FILE* file, vec<scop_p> scops)
201 int i;
203 scop_p scop;
205 FOR_EACH_VEC_ELT (scops, i, scop)
206 print_graphite_scop_statistics (file, scop);
208 /* Print the loop structure. */
209 print_loops (file, 2);
210 print_loops (file, 3);
213 /* Initialize graphite: when there are no loops returns false. */
215 static bool
216 graphite_initialize (isl_ctx *ctx)
218 int min_loops = PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION);
219 int max_bbs = PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION);
220 int nbbs = n_basic_blocks_for_fn (cfun);
221 int nloops = number_of_loops (cfun);
223 if (nloops <= min_loops
224 /* FIXME: This limit on the number of basic blocks of a function
225 should be removed when the SCOP detection is faster. */
226 || (nbbs > max_bbs))
228 if (dump_file && (dump_flags & TDF_DETAILS))
230 if (nloops <= min_loops)
231 fprintf (dump_file, "\nFunction does not have enough loops: "
232 "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n",
233 min_loops);
235 else if (nbbs > max_bbs)
236 fprintf (dump_file, "\nFunction has too many basic blocks: "
237 "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs);
239 fprintf (dump_file, "\nnumber of SCoPs: 0\n");
240 print_global_statistics (dump_file);
243 isl_ctx_free (ctx);
244 return false;
247 scev_reset ();
248 recompute_all_dominators ();
249 initialize_original_copy_tables ();
251 if (dump_file && dump_flags)
253 dump_function_to_file (current_function_decl, dump_file, dump_flags);
254 print_loops (dump_file, 3);
257 return true;
260 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
261 true. */
263 static void
264 graphite_finalize (bool need_cfg_cleanup_p)
266 free_dominance_info (CDI_POST_DOMINATORS);
267 if (need_cfg_cleanup_p)
269 free_dominance_info (CDI_DOMINATORS);
270 scev_reset ();
271 cleanup_tree_cfg ();
272 profile_status_for_fn (cfun) = PROFILE_ABSENT;
273 release_recorded_exits (cfun);
274 tree_estimate_probability (false);
277 free_original_copy_tables ();
279 if (dump_file && dump_flags)
280 print_loops (dump_file, 3);
283 /* Deletes all scops in SCOPS. */
285 static void
286 free_scops (vec<scop_p> scops)
288 int i;
289 scop_p scop;
291 FOR_EACH_VEC_ELT (scops, i, scop)
292 free_scop (scop);
294 scops.release ();
297 isl_ctx *the_isl_ctx;
299 /* Perform a set of linear transforms on the loops of the current
300 function. */
302 void
303 graphite_transform_loops (void)
305 int i;
306 scop_p scop;
307 bool need_cfg_cleanup_p = false;
308 vec<scop_p> scops = vNULL;
309 isl_ctx *ctx;
311 /* If a function is parallel it was most probably already run through graphite
312 once. No need to run again. */
313 if (parallelized_function_p (cfun->decl))
314 return;
316 ctx = isl_ctx_alloc ();
317 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
318 if (!graphite_initialize (ctx))
319 return;
321 the_isl_ctx = ctx;
322 build_scops (&scops);
324 if (dump_file && (dump_flags & TDF_DETAILS))
326 print_graphite_statistics (dump_file, scops);
327 print_global_statistics (dump_file);
330 FOR_EACH_VEC_ELT (scops, i, scop)
331 if (dbg_cnt (graphite_scop))
333 scop->isl_context = ctx;
334 if (!build_poly_scop (scop))
335 continue;
337 if (!apply_poly_transforms (scop))
338 continue;
340 need_cfg_cleanup_p = true;
341 /* When code generation is not successful, do not continue
342 generating code for the next scops: the IR has to be cleaned up
343 and could be in an inconsistent state. */
344 if (!graphite_regenerate_ast_isl (scop))
345 break;
347 location_t loc = find_loop_location
348 (scop->scop_info->region.entry->dest->loop_father);
349 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
350 "loop nest optimized\n");
353 free_scops (scops);
354 graphite_finalize (need_cfg_cleanup_p);
355 the_isl_ctx = NULL;
356 isl_ctx_free (ctx);
359 #else /* If isl is not available: #ifndef HAVE_isl. */
361 static void
362 graphite_transform_loops (void)
364 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
367 #endif
370 static unsigned int
371 graphite_transforms (struct function *fun)
373 if (number_of_loops (fun) <= 1)
374 return 0;
376 graphite_transform_loops ();
378 return 0;
381 static bool
382 gate_graphite_transforms (void)
384 /* Enable -fgraphite pass if any one of the graphite optimization flags
385 is turned on. */
386 if (flag_graphite_identity
387 || flag_loop_parallelize_all
388 || flag_loop_nest_optimize)
389 flag_graphite = 1;
391 return flag_graphite != 0;
394 namespace {
396 const pass_data pass_data_graphite =
398 GIMPLE_PASS, /* type */
399 "graphite0", /* name */
400 OPTGROUP_LOOP, /* optinfo_flags */
401 TV_GRAPHITE, /* tv_id */
402 ( PROP_cfg | PROP_ssa ), /* properties_required */
403 0, /* properties_provided */
404 0, /* properties_destroyed */
405 0, /* todo_flags_start */
406 0, /* todo_flags_finish */
409 class pass_graphite : public gimple_opt_pass
411 public:
412 pass_graphite (gcc::context *ctxt)
413 : gimple_opt_pass (pass_data_graphite, ctxt)
416 /* opt_pass methods: */
417 virtual bool gate (function *) { return gate_graphite_transforms (); }
419 }; // class pass_graphite
421 } // anon namespace
423 gimple_opt_pass *
424 make_pass_graphite (gcc::context *ctxt)
426 return new pass_graphite (ctxt);
429 namespace {
431 const pass_data pass_data_graphite_transforms =
433 GIMPLE_PASS, /* type */
434 "graphite", /* name */
435 OPTGROUP_LOOP, /* optinfo_flags */
436 TV_GRAPHITE_TRANSFORMS, /* tv_id */
437 ( PROP_cfg | PROP_ssa ), /* properties_required */
438 0, /* properties_provided */
439 0, /* properties_destroyed */
440 0, /* todo_flags_start */
441 0, /* todo_flags_finish */
444 class pass_graphite_transforms : public gimple_opt_pass
446 public:
447 pass_graphite_transforms (gcc::context *ctxt)
448 : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
451 /* opt_pass methods: */
452 virtual bool gate (function *) { return gate_graphite_transforms (); }
453 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
455 }; // class pass_graphite_transforms
457 } // anon namespace
459 gimple_opt_pass *
460 make_pass_graphite_transforms (gcc::context *ctxt)
462 return new pass_graphite_transforms (ctxt);