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"
60 /* Print global statistics to FILE. */
63 print_global_statistics (FILE* file
)
68 long n_conditions
= 0;
69 profile_count n_p_bbs
= profile_count::zero ();
70 profile_count n_p_loops
= profile_count::zero ();
71 profile_count n_p_stmts
= profile_count::zero ();
72 profile_count n_p_conditions
= profile_count::zero ();
76 FOR_ALL_BB_FN (bb
, cfun
)
78 gimple_stmt_iterator psi
;
81 if (bb
->count
.initialized_p ())
84 /* Ignore artificial surrounding loop. */
85 if (bb
== bb
->loop_father
->header
89 n_p_loops
+= bb
->count
;
92 if (EDGE_COUNT (bb
->succs
) > 1)
95 if (bb
->count
.initialized_p ())
96 n_p_conditions
+= bb
->count
;
99 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
102 if (bb
->count
.initialized_p ())
103 n_p_stmts
+= bb
->count
;
107 fprintf (file
, "\nGlobal statistics (");
108 fprintf (file
, "BBS:%ld, ", n_bbs
);
109 fprintf (file
, "LOOPS:%ld, ", n_loops
);
110 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
111 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
112 fprintf (file
, "\nGlobal profiling statistics (");
113 fprintf (file
, "BBS:");
115 fprintf (file
, ", LOOPS:");
116 n_p_loops
.dump (file
);
117 fprintf (file
, ", CONDITIONS:");
118 n_p_conditions
.dump (file
);
119 fprintf (file
, ", STMTS:");
120 n_p_stmts
.dump (file
);
121 fprintf (file
, ")\n");
124 /* Print statistics for SCOP to FILE. */
127 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
132 long n_conditions
= 0;
133 profile_count n_p_bbs
= profile_count::zero ();
134 profile_count n_p_loops
= profile_count::zero ();
135 profile_count n_p_stmts
= profile_count::zero ();
136 profile_count n_p_conditions
= profile_count::zero ();
140 FOR_ALL_BB_FN (bb
, cfun
)
142 gimple_stmt_iterator psi
;
143 loop_p loop
= bb
->loop_father
;
145 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
149 if (bb
->count
.initialized_p ())
150 n_p_bbs
+= bb
->count
;
152 if (EDGE_COUNT (bb
->succs
) > 1)
155 n_p_conditions
+= bb
->count
;
158 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
161 n_p_stmts
+= bb
->count
;
164 if (loop
->header
== bb
&& loop_in_sese_p (loop
, scop
->scop_info
->region
))
167 n_p_loops
+= bb
->count
;
171 fprintf (file
, "\nFunction Name: %s\n", current_function_name ());
173 edge scop_begin
= scop
->scop_info
->region
.entry
;
174 edge scop_end
= scop
->scop_info
->region
.exit
;
176 fprintf (file
, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
177 scop_begin
->src
->index
, scop_begin
->dest
->index
);
178 fprintf (file
, "exit_edge (bb_%d, bb_%d))",
179 scop_end
->src
->index
, scop_end
->dest
->index
);
181 fprintf (file
, "\nSCoP statistics (");
182 fprintf (file
, "BBS:%ld, ", n_bbs
);
183 fprintf (file
, "LOOPS:%ld, ", n_loops
);
184 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
185 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
186 fprintf (file
, "\nSCoP profiling statistics (");
187 fprintf (file
, "BBS:");
189 fprintf (file
, ", LOOPS:");
190 n_p_loops
.dump (file
);
191 fprintf (file
, ", CONDITIONS:");
192 n_p_conditions
.dump (file
);
193 fprintf (file
, ", STMTS:");
194 n_p_stmts
.dump (file
);
195 fprintf (file
, ")\n");
198 /* Print statistics for SCOPS to FILE. */
201 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
207 FOR_EACH_VEC_ELT (scops
, i
, scop
)
208 print_graphite_scop_statistics (file
, scop
);
210 /* Print the loop structure. */
211 print_loops (file
, 2);
212 print_loops (file
, 3);
215 /* Initialize graphite: when there are no loops returns false. */
218 graphite_initialize (void)
220 int min_loops
= PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION
);
221 int max_bbs
= PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION
);
222 int nbbs
= n_basic_blocks_for_fn (cfun
);
223 int nloops
= number_of_loops (cfun
);
225 if (nloops
<= min_loops
226 /* FIXME: This limit on the number of basic blocks of a function
227 should be removed when the SCOP detection is faster. */
230 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
232 if (nloops
<= min_loops
)
233 fprintf (dump_file
, "\nFunction does not have enough loops: "
234 "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n",
237 else if (nbbs
> max_bbs
)
238 fprintf (dump_file
, "\nFunction has too many basic blocks: "
239 "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs
);
241 fprintf (dump_file
, "\nnumber of SCoPs: 0\n");
242 print_global_statistics (dump_file
);
248 calculate_dominance_info (CDI_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);
260 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
264 graphite_finalize (bool need_cfg_cleanup_p
)
266 if (need_cfg_cleanup_p
)
268 free_dominance_info (CDI_DOMINATORS
);
271 profile_status_for_fn (cfun
) = PROFILE_ABSENT
;
272 release_recorded_exits (cfun
);
273 tree_estimate_probability (false);
276 free_original_copy_tables ();
278 if (dump_file
&& dump_flags
)
279 print_loops (dump_file
, 3);
282 /* Deletes all scops in SCOPS. */
285 free_scops (vec
<scop_p
> scops
)
290 FOR_EACH_VEC_ELT (scops
, i
, scop
)
296 /* Transforms LOOP to the canonical loop closed SSA form. */
299 canonicalize_loop_closed_ssa (loop_p loop
)
301 edge e
= single_exit (loop
);
305 if (!e
|| (e
->flags
& EDGE_COMPLEX
))
310 /* Make the loop-close PHI node BB contain only PHIs and have a
311 single predecessor. */
312 if (single_pred_p (bb
))
314 e
= split_block_after_labels (bb
);
319 basic_block close
= split_edge (e
);
320 e
= single_succ_edge (close
);
321 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
323 gphi
*phi
= psi
.phi ();
324 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
325 tree arg
= USE_FROM_PTR (use_p
);
327 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
328 if (TREE_CODE (arg
) != SSA_NAME
329 || loop_containing_stmt (SSA_NAME_DEF_STMT (arg
)) != loop
)
332 tree res
= copy_ssa_name (arg
);
333 gphi
*close_phi
= create_phi_node (res
, close
);
334 add_phi_arg (close_phi
, arg
, gimple_phi_arg_edge (close_phi
, 0),
336 SET_USE (use_p
, res
);
341 /* Eliminate duplicates. This relies on processing loops from
342 innermost to outer. */
343 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
345 gphi_iterator gsi
= psi
;
346 gphi
*phi
= psi
.phi ();
348 /* At this point, PHI should be a close phi in normal form. */
349 gcc_assert (gimple_phi_num_args (phi
) == 1);
351 /* Iterate over the next phis and remove duplicates. */
353 while (!gsi_end_p (gsi
))
354 if (gimple_phi_arg_def (phi
, 0) == gimple_phi_arg_def (gsi
.phi (), 0))
356 replace_uses_by (gimple_phi_result (gsi
.phi ()),
357 gimple_phi_result (phi
));
358 remove_phi_node (&gsi
, true);
365 /* Converts the current loop closed SSA form to a canonical form
366 expected by the Graphite code generation.
368 The loop closed SSA form has the following invariant: a variable
369 defined in a loop that is used outside the loop appears only in the
370 phi nodes in the destination of the loop exit. These phi nodes are
371 called close phi nodes.
373 The canonical loop closed SSA form contains the extra invariants:
375 - when the loop contains only one exit, the close phi nodes contain
376 only one argument. That implies that the basic block that contains
377 the close phi nodes has only one predecessor, that is a basic block
380 - the basic block containing the close phi nodes does not contain
383 - there exist only one phi node per definition in the loop.
387 canonicalize_loop_closed_ssa_form (void)
390 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
391 canonicalize_loop_closed_ssa (loop
);
393 checking_verify_loop_closed_ssa (true);
396 isl_ctx
*the_isl_ctx
;
398 /* Perform a set of linear transforms on the loops of the current
402 graphite_transform_loops (void)
406 bool need_cfg_cleanup_p
= false;
407 vec
<scop_p
> scops
= vNULL
;
410 /* If a function is parallel it was most probably already run through graphite
411 once. No need to run again. */
412 if (parallelized_function_p (cfun
->decl
))
415 if (!graphite_initialize ())
418 ctx
= isl_ctx_alloc ();
419 isl_options_set_on_error (ctx
, ISL_ON_ERROR_ABORT
);
422 canonicalize_loop_closed_ssa_form ();
424 calculate_dominance_info (CDI_POST_DOMINATORS
);
425 build_scops (&scops
);
426 free_dominance_info (CDI_POST_DOMINATORS
);
428 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
430 print_graphite_statistics (dump_file
, scops
);
431 print_global_statistics (dump_file
);
434 FOR_EACH_VEC_ELT (scops
, i
, scop
)
435 if (dbg_cnt (graphite_scop
))
437 scop
->isl_context
= ctx
;
438 if (!build_poly_scop (scop
))
441 if (!apply_poly_transforms (scop
))
444 location_t loc
= find_loop_location
445 (scops
[i
]->scop_info
->region
.entry
->dest
->loop_father
);
447 need_cfg_cleanup_p
= true;
448 if (!graphite_regenerate_ast_isl (scop
))
449 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
450 "loop nest not optimized, code generation error\n");
452 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
453 "loop nest optimized\n");
456 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
459 int num_no_dependency
= 0;
461 FOR_EACH_LOOP (loop
, 0)
462 if (loop
->can_be_parallel
)
465 fprintf (dump_file
, "%d loops carried no dependency.\n",
470 graphite_finalize (need_cfg_cleanup_p
);
475 #else /* If isl is not available: #ifndef HAVE_isl. */
478 graphite_transform_loops (void)
480 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
487 graphite_transforms (struct function
*fun
)
489 if (number_of_loops (fun
) <= 1)
492 graphite_transform_loops ();
498 gate_graphite_transforms (void)
500 /* Enable -fgraphite pass if any one of the graphite optimization flags
502 if (flag_graphite_identity
503 || flag_loop_parallelize_all
504 || flag_loop_nest_optimize
)
507 return flag_graphite
!= 0;
512 const pass_data pass_data_graphite
=
514 GIMPLE_PASS
, /* type */
515 "graphite0", /* name */
516 OPTGROUP_LOOP
, /* optinfo_flags */
517 TV_GRAPHITE
, /* tv_id */
518 ( PROP_cfg
| PROP_ssa
), /* properties_required */
519 0, /* properties_provided */
520 0, /* properties_destroyed */
521 0, /* todo_flags_start */
522 0, /* todo_flags_finish */
525 class pass_graphite
: public gimple_opt_pass
528 pass_graphite (gcc::context
*ctxt
)
529 : gimple_opt_pass (pass_data_graphite
, ctxt
)
532 /* opt_pass methods: */
533 virtual bool gate (function
*) { return gate_graphite_transforms (); }
535 }; // class pass_graphite
540 make_pass_graphite (gcc::context
*ctxt
)
542 return new pass_graphite (ctxt
);
547 const pass_data pass_data_graphite_transforms
=
549 GIMPLE_PASS
, /* type */
550 "graphite", /* name */
551 OPTGROUP_LOOP
, /* optinfo_flags */
552 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
553 ( PROP_cfg
| PROP_ssa
), /* properties_required */
554 0, /* properties_provided */
555 0, /* properties_destroyed */
556 0, /* todo_flags_start */
557 0, /* todo_flags_finish */
560 class pass_graphite_transforms
: public gimple_opt_pass
563 pass_graphite_transforms (gcc::context
*ctxt
)
564 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
567 /* opt_pass methods: */
568 virtual bool gate (function
*) { return gate_graphite_transforms (); }
569 virtual unsigned int execute (function
*fun
) { return graphite_transforms (fun
); }
571 }; // class pass_graphite_transforms
576 make_pass_graphite_transforms (gcc::context
*ctxt
)
578 return new pass_graphite_transforms (ctxt
);