c++: new-expression is potentially constant in C++20
[official-gcc.git] / gcc / graphite.cc
blobab8683b5b4190717fb7d9255801ff07286639476
1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2022 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 INCLUDE_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 "pretty-print.h"
40 #include "cfganal.h"
42 #ifdef HAVE_isl
43 #include "cfghooks.h"
44 #include "tree.h"
45 #include "gimple.h"
46 #include "ssa.h"
47 #include "fold-const.h"
48 #include "gimple-iterator.h"
49 #include "tree-cfg.h"
50 #include "tree-ssa-loop.h"
51 #include "tree-data-ref.h"
52 #include "tree-scalar-evolution.h"
53 #include "dbgcnt.h"
54 #include "tree-parloops.h"
55 #include "tree-cfgcleanup.h"
56 #include "tree-vectorizer.h"
57 #include "tree-ssa-loop-manip.h"
58 #include "tree-ssa.h"
59 #include "tree-into-ssa.h"
60 #include "graphite.h"
62 /* Print global statistics to FILE. */
64 static void
65 print_global_statistics (FILE* file)
67 long n_bbs = 0;
68 long n_loops = 0;
69 long n_stmts = 0;
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 ();
76 basic_block bb;
78 FOR_ALL_BB_FN (bb, cfun)
80 gimple_stmt_iterator psi;
82 n_bbs++;
83 if (bb->count.initialized_p ())
84 n_p_bbs += bb->count;
86 /* Ignore artificial surrounding loop. */
87 if (bb == bb->loop_father->header
88 && bb->index != 0)
90 n_loops++;
91 n_p_loops += bb->count;
94 if (EDGE_COUNT (bb->succs) > 1)
96 n_conditions++;
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))
103 n_stmts++;
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:");
116 n_p_bbs.dump (file);
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. */
128 static void
129 print_graphite_scop_statistics (FILE* file, scop_p scop)
131 long n_bbs = 0;
132 long n_loops = 0;
133 long n_stmts = 0;
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 ();
140 basic_block bb;
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))
148 continue;
150 n_bbs++;
151 if (bb->count.initialized_p ())
152 n_p_bbs += bb->count;
154 if (EDGE_COUNT (bb->succs) > 1)
156 n_conditions++;
157 n_p_conditions += bb->count;
160 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
162 n_stmts++;
163 n_p_stmts += bb->count;
166 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
168 n_loops++;
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:");
190 n_p_bbs.dump (file);
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. */
202 static void
203 print_graphite_statistics (FILE* file, vec<scop_p> scops)
205 int i;
206 scop_p scop;
208 FOR_EACH_VEC_ELT (scops, i, scop)
209 print_graphite_scop_statistics (file, scop);
212 struct seir_cache_key
214 hashval_t hash;
215 int entry_dest;
216 int exit_src;
217 int loop_num;
218 tree expr;
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; }
226 static bool
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 const bool empty_zero_p = false;
237 static void mark_empty (seir_cache_key &key) { key.entry_dest = 0; }
238 static bool is_deleted (const seir_cache_key &key) { return !key.expr; }
239 static bool is_empty (const seir_cache_key &key) { return key.entry_dest == 0; }
242 static hash_map<sese_scev_hash, tree> *seir_cache;
244 /* Same as scalar_evolution_in_region but caches results so we avoid
245 re-computing evolutions during transform phase. */
247 tree
248 cached_scalar_evolution_in_region (const sese_l &region, loop_p loop,
249 tree expr)
251 seir_cache_key key;
252 key.entry_dest = region.entry->dest->index;
253 key.exit_src = region.exit->src->index;
254 key.loop_num = loop->num;
255 key.expr = expr;
256 inchash::hash hstate (0);
257 hstate.add_int (key.entry_dest);
258 hstate.add_int (key.exit_src);
259 hstate.add_int (key.loop_num);
260 inchash::add_expr (key.expr, hstate);
261 key.hash = hstate.end ();
263 bool existed;
264 tree &chrec = seir_cache->get_or_insert (key, &existed);
265 if (!existed)
266 chrec = scalar_evolution_in_region (region, loop, expr);
267 return chrec;
270 /* Deletes all scops in SCOPS. */
272 static void
273 free_scops (vec<scop_p> scops)
275 int i;
276 scop_p scop;
278 FOR_EACH_VEC_ELT (scops, i, scop)
279 free_scop (scop);
281 scops.release ();
284 /* Transforms LOOP to the canonical loop closed SSA form. */
286 static void
287 canonicalize_loop_closed_ssa (loop_p loop, edge e)
289 basic_block bb;
290 gphi_iterator psi;
292 bb = e->dest;
294 /* Make the loop-close PHI node BB contain only PHIs and have a
295 single predecessor. */
296 if (single_pred_p (bb))
298 e = split_block_after_labels (bb);
299 bb = e->src;
301 else
303 basic_block close = split_edge (e);
304 e = single_succ_edge (close);
305 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
307 gphi *phi = psi.phi ();
308 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
309 tree arg = USE_FROM_PTR (use_p);
311 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
312 if (TREE_CODE (arg) != SSA_NAME
313 || SSA_NAME_IS_DEFAULT_DEF (arg)
314 || ! flow_bb_inside_loop_p (loop,
315 gimple_bb (SSA_NAME_DEF_STMT (arg))))
316 continue;
318 tree res = copy_ssa_name (arg);
319 gphi *close_phi = create_phi_node (res, close);
320 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
321 UNKNOWN_LOCATION);
322 SET_USE (use_p, res);
324 bb = close;
327 /* Eliminate duplicates. This relies on processing loops from
328 innermost to outer. */
329 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
331 gphi_iterator gsi = psi;
332 gphi *phi = psi.phi ();
334 /* At this point, PHI should be a close phi in normal form. */
335 gcc_assert (gimple_phi_num_args (phi) == 1);
337 /* Iterate over the next phis and remove duplicates. */
338 gsi_next (&gsi);
339 while (!gsi_end_p (gsi))
340 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0))
342 replace_uses_by (gimple_phi_result (gsi.phi ()),
343 gimple_phi_result (phi));
344 remove_phi_node (&gsi, true);
346 else
347 gsi_next (&gsi);
351 /* Converts the current loop closed SSA form to a canonical form
352 expected by the Graphite code generation.
354 The loop closed SSA form has the following invariant: a variable
355 defined in a loop that is used outside the loop appears only in the
356 phi nodes in the destination of the loop exit. These phi nodes are
357 called close phi nodes.
359 The canonical loop closed SSA form contains the extra invariants:
361 - when the loop contains only one exit, the close phi nodes contain
362 only one argument. That implies that the basic block that contains
363 the close phi nodes has only one predecessor, that is a basic block
364 in the loop.
366 - the basic block containing the close phi nodes does not contain
367 other statements.
369 - there exist only one phi node per definition in the loop.
371 In addition to that we also make sure that loop exit edges are
372 first in the successor edge vector. This is to make RPO order
373 as computed by pre_and_rev_post_order_compute be consistent with
374 what initial schedule generation expects.
377 static void
378 canonicalize_loop_form (void)
380 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
382 edge e = single_exit (loop);
383 if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE)))
384 continue;
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))
391 unsigned ei;
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. */
400 scev_reset ();
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
408 function. */
410 void
411 graphite_transform_loops (void)
413 int i;
414 scop_p scop;
415 bool changed = false;
416 vec<scop_p> scops = vNULL;
417 isl_ctx *ctx;
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))
422 return;
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);
432 the_isl_ctx = ctx;
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))
465 continue;
467 if (!apply_poly_transforms (scop))
468 continue;
470 changed = true;
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");
481 delete seir_cache;
482 seir_cache = NULL;
484 if (changed)
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);
490 scev_reset ();
491 checking_verify_loop_structure ();
494 if (dump_file && (dump_flags & TDF_DETAILS))
496 int num_no_dependency = 0;
498 for (auto loop : loops_list (cfun, 0))
499 if (loop->can_be_parallel)
500 num_no_dependency++;
502 fprintf (dump_file, "%d loops carried no dependency.\n",
503 num_no_dependency);
506 free_scops (scops);
507 the_isl_ctx = NULL;
508 isl_ctx_free (ctx);
510 if (changed)
512 cleanup_tree_cfg ();
513 profile_status_for_fn (cfun) = PROFILE_ABSENT;
514 release_recorded_exits (cfun);
515 tree_estimate_probability (false);
519 #else /* If isl is not available: #ifndef HAVE_isl. */
521 static void
522 graphite_transform_loops (void)
524 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
527 #endif
530 static unsigned int
531 graphite_transforms (struct function *fun)
533 if (number_of_loops (fun) <= 1)
534 return 0;
536 graphite_transform_loops ();
538 return 0;
541 static bool
542 gate_graphite_transforms (void)
544 /* Enable -fgraphite pass if any one of the graphite optimization flags
545 is turned on. */
546 if (flag_graphite_identity
547 || flag_loop_parallelize_all
548 || flag_loop_nest_optimize)
549 flag_graphite = 1;
551 return flag_graphite != 0;
554 namespace {
556 const pass_data pass_data_graphite =
558 GIMPLE_PASS, /* type */
559 "graphite0", /* name */
560 OPTGROUP_LOOP, /* optinfo_flags */
561 TV_GRAPHITE, /* tv_id */
562 ( PROP_cfg | PROP_ssa ), /* properties_required */
563 0, /* properties_provided */
564 0, /* properties_destroyed */
565 0, /* todo_flags_start */
566 0, /* todo_flags_finish */
569 class pass_graphite : public gimple_opt_pass
571 public:
572 pass_graphite (gcc::context *ctxt)
573 : gimple_opt_pass (pass_data_graphite, ctxt)
576 /* opt_pass methods: */
577 virtual bool gate (function *) { return gate_graphite_transforms (); }
579 }; // class pass_graphite
581 } // anon namespace
583 gimple_opt_pass *
584 make_pass_graphite (gcc::context *ctxt)
586 return new pass_graphite (ctxt);
589 namespace {
591 const pass_data pass_data_graphite_transforms =
593 GIMPLE_PASS, /* type */
594 "graphite", /* name */
595 OPTGROUP_LOOP, /* optinfo_flags */
596 TV_GRAPHITE_TRANSFORMS, /* tv_id */
597 ( PROP_cfg | PROP_ssa ), /* properties_required */
598 0, /* properties_provided */
599 0, /* properties_destroyed */
600 0, /* todo_flags_start */
601 0, /* todo_flags_finish */
604 class pass_graphite_transforms : public gimple_opt_pass
606 public:
607 pass_graphite_transforms (gcc::context *ctxt)
608 : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
611 /* opt_pass methods: */
612 virtual bool gate (function *) { return gate_graphite_transforms (); }
613 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
615 }; // class pass_graphite_transforms
617 } // anon namespace
619 gimple_opt_pass *
620 make_pass_graphite_transforms (gcc::context *ctxt)
622 return new pass_graphite_transforms (ctxt);