2018-02-04 Paul Thomas <pault@gcc.gnu.org>
[official-gcc.git] / gcc / graphite.c
blobbcf48284f755744043e67581b7d9d137d6015fa7
1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2018 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"
41 #include "cfganal.h"
43 #ifdef HAVE_isl
44 #include "cfghooks.h"
45 #include "tree.h"
46 #include "gimple.h"
47 #include "ssa.h"
48 #include "fold-const.h"
49 #include "gimple-iterator.h"
50 #include "tree-cfg.h"
51 #include "tree-ssa-loop.h"
52 #include "tree-data-ref.h"
53 #include "tree-scalar-evolution.h"
54 #include "dbgcnt.h"
55 #include "tree-parloops.h"
56 #include "tree-cfgcleanup.h"
57 #include "tree-vectorizer.h"
58 #include "tree-ssa-loop-manip.h"
59 #include "tree-ssa.h"
60 #include "tree-into-ssa.h"
61 #include "graphite.h"
63 /* Print global statistics to FILE. */
65 static void
66 print_global_statistics (FILE* file)
68 long n_bbs = 0;
69 long n_loops = 0;
70 long n_stmts = 0;
71 long n_conditions = 0;
72 profile_count n_p_bbs = profile_count::zero ();
73 profile_count n_p_loops = profile_count::zero ();
74 profile_count n_p_stmts = profile_count::zero ();
75 profile_count n_p_conditions = profile_count::zero ();
77 basic_block bb;
79 FOR_ALL_BB_FN (bb, cfun)
81 gimple_stmt_iterator psi;
83 n_bbs++;
84 if (bb->count.initialized_p ())
85 n_p_bbs += bb->count;
87 /* Ignore artificial surrounding loop. */
88 if (bb == bb->loop_father->header
89 && bb->index != 0)
91 n_loops++;
92 n_p_loops += bb->count;
95 if (EDGE_COUNT (bb->succs) > 1)
97 n_conditions++;
98 if (bb->count.initialized_p ())
99 n_p_conditions += bb->count;
102 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
104 n_stmts++;
105 if (bb->count.initialized_p ())
106 n_p_stmts += bb->count;
110 fprintf (file, "\nGlobal statistics (");
111 fprintf (file, "BBS:%ld, ", n_bbs);
112 fprintf (file, "LOOPS:%ld, ", n_loops);
113 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
114 fprintf (file, "STMTS:%ld)\n", n_stmts);
115 fprintf (file, "Global profiling statistics (");
116 fprintf (file, "BBS:");
117 n_p_bbs.dump (file);
118 fprintf (file, ", LOOPS:");
119 n_p_loops.dump (file);
120 fprintf (file, ", CONDITIONS:");
121 n_p_conditions.dump (file);
122 fprintf (file, ", STMTS:");
123 n_p_stmts.dump (file);
124 fprintf (file, ")\n\n");
127 /* Print statistics for SCOP to FILE. */
129 static void
130 print_graphite_scop_statistics (FILE* file, scop_p scop)
132 long n_bbs = 0;
133 long n_loops = 0;
134 long n_stmts = 0;
135 long n_conditions = 0;
136 profile_count n_p_bbs = profile_count::zero ();
137 profile_count n_p_loops = profile_count::zero ();
138 profile_count n_p_stmts = profile_count::zero ();
139 profile_count n_p_conditions = profile_count::zero ();
141 basic_block bb;
143 FOR_ALL_BB_FN (bb, cfun)
145 gimple_stmt_iterator psi;
146 loop_p loop = bb->loop_father;
148 if (!bb_in_sese_p (bb, scop->scop_info->region))
149 continue;
151 n_bbs++;
152 if (bb->count.initialized_p ())
153 n_p_bbs += bb->count;
155 if (EDGE_COUNT (bb->succs) > 1)
157 n_conditions++;
158 n_p_conditions += bb->count;
161 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
163 n_stmts++;
164 n_p_stmts += bb->count;
167 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
169 n_loops++;
170 n_p_loops += bb->count;
174 fprintf (file, "\nFunction Name: %s\n", current_function_name ());
176 edge scop_begin = scop->scop_info->region.entry;
177 edge scop_end = scop->scop_info->region.exit;
179 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
180 scop_begin->src->index, scop_begin->dest->index);
181 fprintf (file, "exit_edge (bb_%d, bb_%d))",
182 scop_end->src->index, scop_end->dest->index);
184 fprintf (file, "\nSCoP statistics (");
185 fprintf (file, "BBS:%ld, ", n_bbs);
186 fprintf (file, "LOOPS:%ld, ", n_loops);
187 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
188 fprintf (file, "STMTS:%ld)\n", n_stmts);
189 fprintf (file, "SCoP profiling statistics (");
190 fprintf (file, "BBS:");
191 n_p_bbs.dump (file);
192 fprintf (file, ", LOOPS:");
193 n_p_loops.dump (file);
194 fprintf (file, ", CONDITIONS:");
195 n_p_conditions.dump (file);
196 fprintf (file, ", STMTS:");
197 n_p_stmts.dump (file);
198 fprintf (file, ")\n\n");
201 /* Print statistics for SCOPS to FILE. */
203 static void
204 print_graphite_statistics (FILE* file, vec<scop_p> scops)
206 int i;
207 scop_p scop;
209 FOR_EACH_VEC_ELT (scops, i, scop)
210 print_graphite_scop_statistics (file, scop);
213 /* Deletes all scops in SCOPS. */
215 static void
216 free_scops (vec<scop_p> scops)
218 int i;
219 scop_p scop;
221 FOR_EACH_VEC_ELT (scops, i, scop)
222 free_scop (scop);
224 scops.release ();
227 /* Transforms LOOP to the canonical loop closed SSA form. */
229 static void
230 canonicalize_loop_closed_ssa (loop_p loop, edge e)
232 basic_block bb;
233 gphi_iterator psi;
235 bb = e->dest;
237 /* Make the loop-close PHI node BB contain only PHIs and have a
238 single predecessor. */
239 if (single_pred_p (bb))
241 e = split_block_after_labels (bb);
242 bb = e->src;
244 else
246 basic_block close = split_edge (e);
247 e = single_succ_edge (close);
248 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
250 gphi *phi = psi.phi ();
251 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
252 tree arg = USE_FROM_PTR (use_p);
254 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
255 if (TREE_CODE (arg) != SSA_NAME
256 || SSA_NAME_IS_DEFAULT_DEF (arg)
257 || ! flow_bb_inside_loop_p (loop,
258 gimple_bb (SSA_NAME_DEF_STMT (arg))))
259 continue;
261 tree res = copy_ssa_name (arg);
262 gphi *close_phi = create_phi_node (res, close);
263 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
264 UNKNOWN_LOCATION);
265 SET_USE (use_p, res);
267 bb = close;
270 /* Eliminate duplicates. This relies on processing loops from
271 innermost to outer. */
272 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
274 gphi_iterator gsi = psi;
275 gphi *phi = psi.phi ();
277 /* At this point, PHI should be a close phi in normal form. */
278 gcc_assert (gimple_phi_num_args (phi) == 1);
280 /* Iterate over the next phis and remove duplicates. */
281 gsi_next (&gsi);
282 while (!gsi_end_p (gsi))
283 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0))
285 replace_uses_by (gimple_phi_result (gsi.phi ()),
286 gimple_phi_result (phi));
287 remove_phi_node (&gsi, true);
289 else
290 gsi_next (&gsi);
294 /* Converts the current loop closed SSA form to a canonical form
295 expected by the Graphite code generation.
297 The loop closed SSA form has the following invariant: a variable
298 defined in a loop that is used outside the loop appears only in the
299 phi nodes in the destination of the loop exit. These phi nodes are
300 called close phi nodes.
302 The canonical loop closed SSA form contains the extra invariants:
304 - when the loop contains only one exit, the close phi nodes contain
305 only one argument. That implies that the basic block that contains
306 the close phi nodes has only one predecessor, that is a basic block
307 in the loop.
309 - the basic block containing the close phi nodes does not contain
310 other statements.
312 - there exist only one phi node per definition in the loop.
314 In addition to that we also make sure that loop exit edges are
315 first in the successor edge vector. This is to make RPO order
316 as computed by pre_and_rev_post_order_compute be consistent with
317 what initial schedule generation expects.
320 static void
321 canonicalize_loop_form (void)
323 loop_p loop;
324 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
326 edge e = single_exit (loop);
327 if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE)))
328 continue;
330 canonicalize_loop_closed_ssa (loop, e);
332 /* If the exit is not first in the edge vector make it so. */
333 if (e != EDGE_SUCC (e->src, 0))
335 unsigned ei;
336 for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei)
338 std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0));
342 /* We can end up releasing duplicate exit PHIs and also introduce
343 additional copies so the cached information isn't correct anymore. */
344 scev_reset ();
346 checking_verify_loop_closed_ssa (true);
349 isl_ctx *the_isl_ctx;
351 /* Perform a set of linear transforms on the loops of the current
352 function. */
354 void
355 graphite_transform_loops (void)
357 int i;
358 scop_p scop;
359 bool changed = false;
360 vec<scop_p> scops = vNULL;
361 isl_ctx *ctx;
363 /* If a function is parallel it was most probably already run through graphite
364 once. No need to run again. */
365 if (parallelized_function_p (cfun->decl))
366 return;
368 calculate_dominance_info (CDI_DOMINATORS);
370 /* We rely on post-dominators during merging of SESE regions so those
371 have to be meaningful. */
372 connect_infinite_loops_to_exit ();
374 ctx = isl_ctx_alloc ();
375 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
376 the_isl_ctx = ctx;
378 sort_sibling_loops (cfun);
379 canonicalize_loop_form ();
381 /* Print the loop structure. */
382 if (dump_file && (dump_flags & TDF_DETAILS))
384 print_loops (dump_file, 2);
385 print_loops (dump_file, 3);
388 calculate_dominance_info (CDI_POST_DOMINATORS);
389 build_scops (&scops);
390 free_dominance_info (CDI_POST_DOMINATORS);
392 /* Remove the fake exits before transform given they are not reflected
393 in loop structures we end up verifying. */
394 remove_fake_exit_edges ();
396 if (dump_file && (dump_flags & TDF_DETAILS))
398 print_graphite_statistics (dump_file, scops);
399 print_global_statistics (dump_file);
402 FOR_EACH_VEC_ELT (scops, i, scop)
403 if (dbg_cnt (graphite_scop))
405 scop->isl_context = ctx;
406 if (!build_poly_scop (scop))
407 continue;
409 if (!apply_poly_transforms (scop))
410 continue;
412 changed = true;
413 if (graphite_regenerate_ast_isl (scop))
415 location_t loc = find_loop_location
416 (scops[i]->scop_info->region.entry->dest->loop_father);
417 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
418 "loop nest optimized\n");
422 if (changed)
424 mark_virtual_operands_for_renaming (cfun);
425 update_ssa (TODO_update_ssa);
426 checking_verify_ssa (true, true);
427 rewrite_into_loop_closed_ssa (NULL, 0);
428 scev_reset ();
429 checking_verify_loop_structure ();
432 if (dump_file && (dump_flags & TDF_DETAILS))
434 loop_p loop;
435 int num_no_dependency = 0;
437 FOR_EACH_LOOP (loop, 0)
438 if (loop->can_be_parallel)
439 num_no_dependency++;
441 fprintf (dump_file, "%d loops carried no dependency.\n",
442 num_no_dependency);
445 free_scops (scops);
446 the_isl_ctx = NULL;
447 isl_ctx_free (ctx);
449 if (changed)
451 cleanup_tree_cfg ();
452 profile_status_for_fn (cfun) = PROFILE_ABSENT;
453 release_recorded_exits (cfun);
454 tree_estimate_probability (false);
458 #else /* If isl is not available: #ifndef HAVE_isl. */
460 static void
461 graphite_transform_loops (void)
463 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
466 #endif
469 static unsigned int
470 graphite_transforms (struct function *fun)
472 if (number_of_loops (fun) <= 1)
473 return 0;
475 graphite_transform_loops ();
477 return 0;
480 static bool
481 gate_graphite_transforms (void)
483 /* Enable -fgraphite pass if any one of the graphite optimization flags
484 is turned on. */
485 if (flag_graphite_identity
486 || flag_loop_parallelize_all
487 || flag_loop_nest_optimize)
488 flag_graphite = 1;
490 return flag_graphite != 0;
493 namespace {
495 const pass_data pass_data_graphite =
497 GIMPLE_PASS, /* type */
498 "graphite0", /* name */
499 OPTGROUP_LOOP, /* optinfo_flags */
500 TV_GRAPHITE, /* tv_id */
501 ( PROP_cfg | PROP_ssa ), /* properties_required */
502 0, /* properties_provided */
503 0, /* properties_destroyed */
504 0, /* todo_flags_start */
505 0, /* todo_flags_finish */
508 class pass_graphite : public gimple_opt_pass
510 public:
511 pass_graphite (gcc::context *ctxt)
512 : gimple_opt_pass (pass_data_graphite, ctxt)
515 /* opt_pass methods: */
516 virtual bool gate (function *) { return gate_graphite_transforms (); }
518 }; // class pass_graphite
520 } // anon namespace
522 gimple_opt_pass *
523 make_pass_graphite (gcc::context *ctxt)
525 return new pass_graphite (ctxt);
528 namespace {
530 const pass_data pass_data_graphite_transforms =
532 GIMPLE_PASS, /* type */
533 "graphite", /* name */
534 OPTGROUP_LOOP, /* optinfo_flags */
535 TV_GRAPHITE_TRANSFORMS, /* tv_id */
536 ( PROP_cfg | PROP_ssa ), /* properties_required */
537 0, /* properties_provided */
538 0, /* properties_destroyed */
539 0, /* todo_flags_start */
540 0, /* todo_flags_finish */
543 class pass_graphite_transforms : public gimple_opt_pass
545 public:
546 pass_graphite_transforms (gcc::context *ctxt)
547 : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
550 /* opt_pass methods: */
551 virtual bool gate (function *) { return gate_graphite_transforms (); }
552 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
554 }; // class pass_graphite_transforms
556 } // anon namespace
558 gimple_opt_pass *
559 make_pass_graphite_transforms (gcc::context *ctxt)
561 return new pass_graphite_transforms (ctxt);