1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2019 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"
39 #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
, "Global 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\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
, "SCoP 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\n");
200 /* Print statistics for SCOPS to FILE. */
203 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
208 FOR_EACH_VEC_ELT (scops
, i
, scop
)
209 print_graphite_scop_statistics (file
, scop
);
212 struct seir_cache_key
221 struct sese_scev_hash
: typed_noop_remove
<seir_cache_key
>
223 typedef seir_cache_key value_type
;
224 typedef seir_cache_key compare_type
;
225 static hashval_t
hash (const seir_cache_key
&key
) { return key
.hash
; }
227 equal (const seir_cache_key
&key1
, const seir_cache_key
&key2
)
229 return (key1
.hash
== key2
.hash
230 && key1
.entry_dest
== key2
.entry_dest
231 && key1
.exit_src
== key2
.exit_src
232 && key1
.loop_num
== key2
.loop_num
233 && operand_equal_p (key1
.expr
, key2
.expr
, 0));
235 static void mark_deleted (seir_cache_key
&key
) { key
.expr
= NULL_TREE
; }
236 static void mark_empty (seir_cache_key
&key
) { key
.entry_dest
= 0; }
237 static bool is_deleted (const seir_cache_key
&key
) { return !key
.expr
; }
238 static bool is_empty (const seir_cache_key
&key
) { return key
.entry_dest
== 0; }
241 static hash_map
<sese_scev_hash
, tree
> *seir_cache
;
243 /* Same as scalar_evolution_in_region but caches results so we avoid
244 re-computing evolutions during transform phase. */
247 cached_scalar_evolution_in_region (const sese_l
®ion
, loop_p loop
,
251 key
.entry_dest
= region
.entry
->dest
->index
;
252 key
.exit_src
= region
.exit
->src
->index
;
253 key
.loop_num
= loop
->num
;
255 inchash::hash
hstate (0);
256 hstate
.add_int (key
.entry_dest
);
257 hstate
.add_int (key
.exit_src
);
258 hstate
.add_int (key
.loop_num
);
259 inchash::add_expr (key
.expr
, hstate
);
260 key
.hash
= hstate
.end ();
263 tree
&chrec
= seir_cache
->get_or_insert (key
, &existed
);
265 chrec
= scalar_evolution_in_region (region
, loop
, expr
);
269 /* Deletes all scops in SCOPS. */
272 free_scops (vec
<scop_p
> scops
)
277 FOR_EACH_VEC_ELT (scops
, i
, scop
)
283 /* Transforms LOOP to the canonical loop closed SSA form. */
286 canonicalize_loop_closed_ssa (loop_p loop
, edge e
)
293 /* Make the loop-close PHI node BB contain only PHIs and have a
294 single predecessor. */
295 if (single_pred_p (bb
))
297 e
= split_block_after_labels (bb
);
302 basic_block close
= split_edge (e
);
303 e
= single_succ_edge (close
);
304 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
306 gphi
*phi
= psi
.phi ();
307 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
308 tree arg
= USE_FROM_PTR (use_p
);
310 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
311 if (TREE_CODE (arg
) != SSA_NAME
312 || SSA_NAME_IS_DEFAULT_DEF (arg
)
313 || ! flow_bb_inside_loop_p (loop
,
314 gimple_bb (SSA_NAME_DEF_STMT (arg
))))
317 tree res
= copy_ssa_name (arg
);
318 gphi
*close_phi
= create_phi_node (res
, close
);
319 add_phi_arg (close_phi
, arg
, gimple_phi_arg_edge (close_phi
, 0),
321 SET_USE (use_p
, res
);
326 /* Eliminate duplicates. This relies on processing loops from
327 innermost to outer. */
328 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
330 gphi_iterator gsi
= psi
;
331 gphi
*phi
= psi
.phi ();
333 /* At this point, PHI should be a close phi in normal form. */
334 gcc_assert (gimple_phi_num_args (phi
) == 1);
336 /* Iterate over the next phis and remove duplicates. */
338 while (!gsi_end_p (gsi
))
339 if (gimple_phi_arg_def (phi
, 0) == gimple_phi_arg_def (gsi
.phi (), 0))
341 replace_uses_by (gimple_phi_result (gsi
.phi ()),
342 gimple_phi_result (phi
));
343 remove_phi_node (&gsi
, true);
350 /* Converts the current loop closed SSA form to a canonical form
351 expected by the Graphite code generation.
353 The loop closed SSA form has the following invariant: a variable
354 defined in a loop that is used outside the loop appears only in the
355 phi nodes in the destination of the loop exit. These phi nodes are
356 called close phi nodes.
358 The canonical loop closed SSA form contains the extra invariants:
360 - when the loop contains only one exit, the close phi nodes contain
361 only one argument. That implies that the basic block that contains
362 the close phi nodes has only one predecessor, that is a basic block
365 - the basic block containing the close phi nodes does not contain
368 - there exist only one phi node per definition in the loop.
370 In addition to that we also make sure that loop exit edges are
371 first in the successor edge vector. This is to make RPO order
372 as computed by pre_and_rev_post_order_compute be consistent with
373 what initial schedule generation expects.
377 canonicalize_loop_form (void)
380 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
382 edge e
= single_exit (loop
);
383 if (!e
|| (e
->flags
& (EDGE_COMPLEX
|EDGE_FAKE
)))
386 canonicalize_loop_closed_ssa (loop
, e
);
388 /* If the exit is not first in the edge vector make it so. */
389 if (e
!= EDGE_SUCC (e
->src
, 0))
392 for (ei
= 0; EDGE_SUCC (e
->src
, ei
) != e
; ++ei
)
394 std::swap (EDGE_SUCC (e
->src
, ei
), EDGE_SUCC (e
->src
, 0));
398 /* We can end up releasing duplicate exit PHIs and also introduce
399 additional copies so the cached information isn't correct anymore. */
402 checking_verify_loop_closed_ssa (true);
405 isl_ctx
*the_isl_ctx
;
407 /* Perform a set of linear transforms on the loops of the current
411 graphite_transform_loops (void)
415 bool changed
= false;
416 vec
<scop_p
> scops
= vNULL
;
419 /* If a function is parallel it was most probably already run through graphite
420 once. No need to run again. */
421 if (parallelized_function_p (cfun
->decl
))
424 calculate_dominance_info (CDI_DOMINATORS
);
426 /* We rely on post-dominators during merging of SESE regions so those
427 have to be meaningful. */
428 connect_infinite_loops_to_exit ();
430 ctx
= isl_ctx_alloc ();
431 isl_options_set_on_error (ctx
, ISL_ON_ERROR_ABORT
);
434 sort_sibling_loops (cfun
);
435 canonicalize_loop_form ();
437 /* Print the loop structure. */
438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
440 print_loops (dump_file
, 2);
441 print_loops (dump_file
, 3);
444 seir_cache
= new hash_map
<sese_scev_hash
, tree
>;
446 calculate_dominance_info (CDI_POST_DOMINATORS
);
447 build_scops (&scops
);
448 free_dominance_info (CDI_POST_DOMINATORS
);
450 /* Remove the fake exits before transform given they are not reflected
451 in loop structures we end up verifying. */
452 remove_fake_exit_edges ();
454 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
456 print_graphite_statistics (dump_file
, scops
);
457 print_global_statistics (dump_file
);
460 FOR_EACH_VEC_ELT (scops
, i
, scop
)
461 if (dbg_cnt (graphite_scop
))
463 scop
->isl_context
= ctx
;
464 if (!build_poly_scop (scop
))
467 if (!apply_poly_transforms (scop
))
471 if (graphite_regenerate_ast_isl (scop
)
472 && dump_enabled_p ())
474 dump_user_location_t loc
= find_loop_location
475 (scops
[i
]->scop_info
->region
.entry
->dest
->loop_father
);
476 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
477 "loop nest optimized\n");
486 mark_virtual_operands_for_renaming (cfun
);
487 update_ssa (TODO_update_ssa
);
488 checking_verify_ssa (true, true);
489 rewrite_into_loop_closed_ssa (NULL
, 0);
491 checking_verify_loop_structure ();
494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
497 int num_no_dependency
= 0;
499 FOR_EACH_LOOP (loop
, 0)
500 if (loop
->can_be_parallel
)
503 fprintf (dump_file
, "%d loops carried no dependency.\n",
514 profile_status_for_fn (cfun
) = PROFILE_ABSENT
;
515 release_recorded_exits (cfun
);
516 tree_estimate_probability (false);
520 #else /* If isl is not available: #ifndef HAVE_isl. */
523 graphite_transform_loops (void)
525 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
532 graphite_transforms (struct function
*fun
)
534 if (number_of_loops (fun
) <= 1)
537 graphite_transform_loops ();
543 gate_graphite_transforms (void)
545 /* Enable -fgraphite pass if any one of the graphite optimization flags
547 if (flag_graphite_identity
548 || flag_loop_parallelize_all
549 || flag_loop_nest_optimize
)
552 return flag_graphite
!= 0;
557 const pass_data pass_data_graphite
=
559 GIMPLE_PASS
, /* type */
560 "graphite0", /* name */
561 OPTGROUP_LOOP
, /* optinfo_flags */
562 TV_GRAPHITE
, /* tv_id */
563 ( PROP_cfg
| PROP_ssa
), /* properties_required */
564 0, /* properties_provided */
565 0, /* properties_destroyed */
566 0, /* todo_flags_start */
567 0, /* todo_flags_finish */
570 class pass_graphite
: public gimple_opt_pass
573 pass_graphite (gcc::context
*ctxt
)
574 : gimple_opt_pass (pass_data_graphite
, ctxt
)
577 /* opt_pass methods: */
578 virtual bool gate (function
*) { return gate_graphite_transforms (); }
580 }; // class pass_graphite
585 make_pass_graphite (gcc::context
*ctxt
)
587 return new pass_graphite (ctxt
);
592 const pass_data pass_data_graphite_transforms
=
594 GIMPLE_PASS
, /* type */
595 "graphite", /* name */
596 OPTGROUP_LOOP
, /* optinfo_flags */
597 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
598 ( PROP_cfg
| PROP_ssa
), /* properties_required */
599 0, /* properties_provided */
600 0, /* properties_destroyed */
601 0, /* todo_flags_start */
602 0, /* todo_flags_finish */
605 class pass_graphite_transforms
: public gimple_opt_pass
608 pass_graphite_transforms (gcc::context
*ctxt
)
609 : gimple_opt_pass (pass_data_graphite_transforms
, ctxt
)
612 /* opt_pass methods: */
613 virtual bool gate (function
*) { return gate_graphite_transforms (); }
614 virtual unsigned int execute (function
*fun
) { return graphite_transforms (fun
); }
616 }; // class pass_graphite_transforms
621 make_pass_graphite_transforms (gcc::context
*ctxt
)
623 return new pass_graphite_transforms (ctxt
);