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)
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
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
34 #include "coretypes.h"
36 #include "diagnostic-core.h"
38 #include "tree-pass.h"
40 #include "pretty-print.h"
47 #include "fold-const.h"
48 #include "gimple-iterator.h"
50 #include "tree-ssa-loop.h"
51 #include "tree-data-ref.h"
52 #include "tree-scalar-evolution.h"
54 #include "tree-parloops.h"
55 #include "tree-cfgcleanup.h"
56 #include "tree-vectorizer.h"
57 #include "tree-ssa-loop-manip.h"
59 #include "tree-into-ssa.h"
62 /* Print global statistics to FILE. */
65 print_global_statistics (FILE* file
)
70 long n_conditions
= 0;
71 profile_count n_p_bbs
= profile_count::zero ();
72 profile_count n_p_loops
= profile_count::zero ();
73 profile_count n_p_stmts
= profile_count::zero ();
74 profile_count n_p_conditions
= profile_count::zero ();
78 FOR_ALL_BB_FN (bb
, cfun
)
80 gimple_stmt_iterator psi
;
83 if (bb
->count
.initialized_p ())
86 /* Ignore artificial surrounding loop. */
87 if (bb
== bb
->loop_father
->header
91 n_p_loops
+= bb
->count
;
94 if (EDGE_COUNT (bb
->succs
) > 1)
97 if (bb
->count
.initialized_p ())
98 n_p_conditions
+= bb
->count
;
101 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
104 if (bb
->count
.initialized_p ())
105 n_p_stmts
+= bb
->count
;
109 fprintf (file
, "\nGlobal statistics (");
110 fprintf (file
, "BBS:%ld, ", n_bbs
);
111 fprintf (file
, "LOOPS:%ld, ", n_loops
);
112 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
113 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
114 fprintf (file
, "\nGlobal profiling statistics (");
115 fprintf (file
, "BBS:");
117 fprintf (file
, ", LOOPS:");
118 n_p_loops
.dump (file
);
119 fprintf (file
, ", CONDITIONS:");
120 n_p_conditions
.dump (file
);
121 fprintf (file
, ", STMTS:");
122 n_p_stmts
.dump (file
);
123 fprintf (file
, ")\n");
126 /* Print statistics for SCOP to FILE. */
129 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
134 long n_conditions
= 0;
135 profile_count n_p_bbs
= profile_count::zero ();
136 profile_count n_p_loops
= profile_count::zero ();
137 profile_count n_p_stmts
= profile_count::zero ();
138 profile_count n_p_conditions
= profile_count::zero ();
142 FOR_ALL_BB_FN (bb
, cfun
)
144 gimple_stmt_iterator psi
;
145 loop_p loop
= bb
->loop_father
;
147 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
151 if (bb
->count
.initialized_p ())
152 n_p_bbs
+= bb
->count
;
154 if (EDGE_COUNT (bb
->succs
) > 1)
157 n_p_conditions
+= bb
->count
;
160 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
163 n_p_stmts
+= bb
->count
;
166 if (loop
->header
== bb
&& loop_in_sese_p (loop
, scop
->scop_info
->region
))
169 n_p_loops
+= bb
->count
;
173 fprintf (file
, "\nFunction Name: %s\n", current_function_name ());
175 edge scop_begin
= scop
->scop_info
->region
.entry
;
176 edge scop_end
= scop
->scop_info
->region
.exit
;
178 fprintf (file
, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
179 scop_begin
->src
->index
, scop_begin
->dest
->index
);
180 fprintf (file
, "exit_edge (bb_%d, bb_%d))",
181 scop_end
->src
->index
, scop_end
->dest
->index
);
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:");
191 fprintf (file
, ", LOOPS:");
192 n_p_loops
.dump (file
);
193 fprintf (file
, ", CONDITIONS:");
194 n_p_conditions
.dump (file
);
195 fprintf (file
, ", STMTS:");
196 n_p_stmts
.dump (file
);
197 fprintf (file
, ")\n");
200 /* Print statistics for SCOPS to FILE. */
203 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
209 FOR_EACH_VEC_ELT (scops
, i
, scop
)
210 print_graphite_scop_statistics (file
, scop
);
212 /* Print the loop structure. */
213 print_loops (file
, 2);
214 print_loops (file
, 3);
217 /* Deletes all scops in SCOPS. */
220 free_scops (vec
<scop_p
> scops
)
225 FOR_EACH_VEC_ELT (scops
, i
, scop
)
231 /* Transforms LOOP to the canonical loop closed SSA form. */
234 canonicalize_loop_closed_ssa (loop_p loop
)
236 edge e
= single_exit (loop
);
240 if (!e
|| (e
->flags
& EDGE_COMPLEX
))
245 /* Make the loop-close PHI node BB contain only PHIs and have a
246 single predecessor. */
247 if (single_pred_p (bb
))
249 e
= split_block_after_labels (bb
);
254 basic_block close
= split_edge (e
);
255 e
= single_succ_edge (close
);
256 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
258 gphi
*phi
= psi
.phi ();
259 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
260 tree arg
= USE_FROM_PTR (use_p
);
262 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
263 if (TREE_CODE (arg
) != SSA_NAME
264 || SSA_NAME_IS_DEFAULT_DEF (arg
)
265 || ! flow_bb_inside_loop_p (loop
,
266 gimple_bb (SSA_NAME_DEF_STMT (arg
))))
269 tree res
= copy_ssa_name (arg
);
270 gphi
*close_phi
= create_phi_node (res
, close
);
271 add_phi_arg (close_phi
, arg
, gimple_phi_arg_edge (close_phi
, 0),
273 SET_USE (use_p
, res
);
278 /* Eliminate duplicates. This relies on processing loops from
279 innermost to outer. */
280 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
282 gphi_iterator gsi
= psi
;
283 gphi
*phi
= psi
.phi ();
285 /* At this point, PHI should be a close phi in normal form. */
286 gcc_assert (gimple_phi_num_args (phi
) == 1);
288 /* Iterate over the next phis and remove duplicates. */
290 while (!gsi_end_p (gsi
))
291 if (gimple_phi_arg_def (phi
, 0) == gimple_phi_arg_def (gsi
.phi (), 0))
293 replace_uses_by (gimple_phi_result (gsi
.phi ()),
294 gimple_phi_result (phi
));
295 remove_phi_node (&gsi
, true);
302 /* Converts the current loop closed SSA form to a canonical form
303 expected by the Graphite code generation.
305 The loop closed SSA form has the following invariant: a variable
306 defined in a loop that is used outside the loop appears only in the
307 phi nodes in the destination of the loop exit. These phi nodes are
308 called close phi nodes.
310 The canonical loop closed SSA form contains the extra invariants:
312 - when the loop contains only one exit, the close phi nodes contain
313 only one argument. That implies that the basic block that contains
314 the close phi nodes has only one predecessor, that is a basic block
317 - the basic block containing the close phi nodes does not contain
320 - there exist only one phi node per definition in the loop.
324 canonicalize_loop_closed_ssa_form (void)
327 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
328 canonicalize_loop_closed_ssa (loop
);
330 checking_verify_loop_closed_ssa (true);
333 isl_ctx
*the_isl_ctx
;
335 /* Perform a set of linear transforms on the loops of the current
339 graphite_transform_loops (void)
343 bool changed
= false;
344 vec
<scop_p
> scops
= vNULL
;
347 /* If a function is parallel it was most probably already run through graphite
348 once. No need to run again. */
349 if (parallelized_function_p (cfun
->decl
))
352 calculate_dominance_info (CDI_DOMINATORS
);
354 ctx
= isl_ctx_alloc ();
355 isl_options_set_on_error (ctx
, ISL_ON_ERROR_ABORT
);
358 sort_sibling_loops (cfun
);
359 canonicalize_loop_closed_ssa_form ();
361 calculate_dominance_info (CDI_POST_DOMINATORS
);
362 build_scops (&scops
);
363 free_dominance_info (CDI_POST_DOMINATORS
);
365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
367 print_graphite_statistics (dump_file
, scops
);
368 print_global_statistics (dump_file
);
371 FOR_EACH_VEC_ELT (scops
, i
, scop
)
372 if (dbg_cnt (graphite_scop
))
374 scop
->isl_context
= ctx
;
375 if (!build_poly_scop (scop
))
378 if (!apply_poly_transforms (scop
))
381 location_t loc
= find_loop_location
382 (scops
[i
]->scop_info
->region
.entry
->dest
->loop_father
);
385 if (!graphite_regenerate_ast_isl (scop
))
386 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
387 "loop nest not optimized, code generation error\n");
389 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
390 "loop nest optimized\n");
395 mark_virtual_operands_for_renaming (cfun
);
396 update_ssa (TODO_update_ssa
);
397 checking_verify_ssa (true, true);
398 rewrite_into_loop_closed_ssa (NULL
, 0);
400 checking_verify_loop_structure ();
403 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
406 int num_no_dependency
= 0;
408 FOR_EACH_LOOP (loop
, 0)
409 if (loop
->can_be_parallel
)
412 fprintf (dump_file
, "%d loops carried no dependency.\n",
423 profile_status_for_fn (cfun
) = PROFILE_ABSENT
;
424 release_recorded_exits (cfun
);
425 tree_estimate_probability (false);
430 #else /* If isl is not available: #ifndef HAVE_isl. */
433 graphite_transform_loops (void)
435 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
442 graphite_transforms (struct function
*fun
)
444 if (number_of_loops (fun
) <= 1)
447 graphite_transform_loops ();
453 gate_graphite_transforms (void)
455 /* Enable -fgraphite pass if any one of the graphite optimization flags
457 if (flag_graphite_identity
458 || flag_loop_parallelize_all
459 || flag_loop_nest_optimize
)
462 return flag_graphite
!= 0;
467 const pass_data pass_data_graphite
=
469 GIMPLE_PASS
, /* type */
470 "graphite0", /* name */
471 OPTGROUP_LOOP
, /* optinfo_flags */
472 TV_GRAPHITE
, /* tv_id */
473 ( PROP_cfg
| PROP_ssa
), /* properties_required */
474 0, /* properties_provided */
475 0, /* properties_destroyed */
476 0, /* todo_flags_start */
477 0, /* todo_flags_finish */
480 class pass_graphite
: public gimple_opt_pass
483 pass_graphite (gcc::context
*ctxt
)
484 : gimple_opt_pass (pass_data_graphite
, ctxt
)
487 /* opt_pass methods: */
488 virtual bool gate (function
*) { return gate_graphite_transforms (); }
490 }; // class pass_graphite
495 make_pass_graphite (gcc::context
*ctxt
)
497 return new pass_graphite (ctxt
);
502 const pass_data pass_data_graphite_transforms
=
504 GIMPLE_PASS
, /* type */
505 "graphite", /* name */
506 OPTGROUP_LOOP
, /* optinfo_flags */
507 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
508 ( PROP_cfg
| PROP_ssa
), /* properties_required */
509 0, /* properties_provided */
510 0, /* properties_destroyed */
511 0, /* todo_flags_start */
512 0, /* todo_flags_finish */
515 class pass_graphite_transforms
: public gimple_opt_pass
518 pass_graphite_transforms (gcc::context
*ctxt
)
519 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
522 /* opt_pass methods: */
523 virtual bool gate (function
*) { return gate_graphite_transforms (); }
524 virtual unsigned int execute (function
*fun
) { return graphite_transforms (fun
); }
526 }; // class pass_graphite_transforms
531 make_pass_graphite_transforms (gcc::context
*ctxt
)
533 return new pass_graphite_transforms (ctxt
);