1/* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2023 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21/* This pass converts GIMPLE to GRAPHITE, performs some loop
22 transformations and then converts the resulting representation back
23 to GIMPLE.
24
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. */
29
30#define INCLUDE_ISL
31
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"
41
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 "tree-ssa-propagate.h"
61#include "graphite.h"
62
63/* Print global statistics to FILE. */
64
65static void
66print_global_statistics (FILE* file)
67{
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 ();
76
77 basic_block bb;
78
79 FOR_ALL_BB_FN (bb, cfun)
80 {
81 gimple_stmt_iterator psi;
82
83 n_bbs++;
84 if (bb->count.initialized_p ())
85 n_p_bbs += bb->count;
86
87 /* Ignore artificial surrounding loop. */
88 if (bb == bb->loop_father->header
89 && bb->index != 0)
90 {
91 n_loops++;
92 n_p_loops += bb->count;
93 }
94
95 if (EDGE_COUNT (bb->succs) > 1)
96 {
97 n_conditions++;
98 if (bb->count.initialized_p ())
99 n_p_conditions += bb->count;
100 }
101
102 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
103 {
104 n_stmts++;
105 if (bb->count.initialized_p ())
106 n_p_stmts += bb->count;
107 }
108 }
109
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");
125}
126
127/* Print statistics for SCOP to FILE. */
128
129static void
130print_graphite_scop_statistics (FILE* file, scop_p scop)
131{
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 ();
140
141 basic_block bb;
142
143 FOR_ALL_BB_FN (bb, cfun)
144 {
145 gimple_stmt_iterator psi;
146 loop_p loop = bb->loop_father;
147
148 if (!bb_in_sese_p (bb, scop->scop_info->region))
149 continue;
150
151 n_bbs++;
152 if (bb->count.initialized_p ())
153 n_p_bbs += bb->count;
154
155 if (EDGE_COUNT (bb->succs) > 1)
156 {
157 n_conditions++;
158 n_p_conditions += bb->count;
159 }
160
161 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
162 {
163 n_stmts++;
164 n_p_stmts += bb->count;
165 }
166
167 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
168 {
169 n_loops++;
170 n_p_loops += bb->count;
171 }
172 }
173
174 fprintf (file, "\nFunction Name: %s\n", current_function_name ());
175
176 edge scop_begin = scop->scop_info->region.entry;
177 edge scop_end = scop->scop_info->region.exit;
178
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);
183
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");
199}
200
201/* Print statistics for SCOPS to FILE. */
202
203static void
204print_graphite_statistics (FILE* file, vec<scop_p> scops)
205{
206 int i;
207 scop_p scop;
208
209 FOR_EACH_VEC_ELT (scops, i, scop)
210 print_graphite_scop_statistics (file, scop);
211}
212
213struct seir_cache_key
214{
215 hashval_t hash;
216 int entry_dest;
217 int exit_src;
218 int loop_num;
219 tree expr;
220};
221
222struct sese_scev_hash : typed_noop_remove <seir_cache_key>
223{
224 typedef seir_cache_key value_type;
225 typedef seir_cache_key compare_type;
226 static hashval_t hash (const seir_cache_key &key) { return key.hash; }
227 static bool
228 equal (const seir_cache_key &key1, const seir_cache_key &key2)
229 {
230 return (key1.hash == key2.hash
231 && key1.entry_dest == key2.entry_dest
232 && key1.exit_src == key2.exit_src
233 && key1.loop_num == key2.loop_num
234 && operand_equal_p (key1.expr, key2.expr, 0));
235 }
236 static void mark_deleted (seir_cache_key &key) { key.expr = NULL_TREE; }
237 static const bool empty_zero_p = false;
238 static void mark_empty (seir_cache_key &key) { key.entry_dest = 0; }
239 static bool is_deleted (const seir_cache_key &key) { return !key.expr; }
240 static bool is_empty (const seir_cache_key &key) { return key.entry_dest == 0; }
241};
242
243static hash_map<sese_scev_hash, tree> *seir_cache;
244
245/* Same as scalar_evolution_in_region but caches results so we avoid
246 re-computing evolutions during transform phase. */
247
248tree
249cached_scalar_evolution_in_region (const sese_l &region, loop_p loop,
250 tree expr)
251{
252 seir_cache_key key;
253 key.entry_dest = region.entry->dest->index;
254 key.exit_src = region.exit->src->index;
255 key.loop_num = loop->num;
256 key.expr = expr;
257 inchash::hash hstate (0);
258 hstate.add_int (key.entry_dest);
259 hstate.add_int (key.exit_src);
260 hstate.add_int (key.loop_num);
261 inchash::add_expr (key.expr, hstate);
262 key.hash = hstate.end ();
263
264 bool existed;
265 tree &chrec = seir_cache->get_or_insert (key, &existed);
266 if (!existed)
267 chrec = scalar_evolution_in_region (region, loop, expr);
268 return chrec;
269}
270
271/* Deletes all scops in SCOPS. */
272
273static void
274free_scops (vec<scop_p> scops)
275{
276 int i;
277 scop_p scop;
278
279 FOR_EACH_VEC_ELT (scops, i, scop)
280 free_scop (scop);
281
282 scops.release ();
283}
284
285/* Transforms LOOP to the canonical loop closed SSA form. */
286
287static void
288canonicalize_loop_closed_ssa (loop_p loop, edge e)
289{
290 basic_block bb;
291 gphi_iterator psi;
292
293 bb = e->dest;
294
295 /* Make the loop-close PHI node BB contain only PHIs and have a
296 single predecessor. */
297 if (single_pred_p (bb))
298 {
299 e = split_block_after_labels (bb);
300 bb = e->src;
301 }
302 else
303 {
304 basic_block close = split_edge (e);
305 e = single_succ_edge (close);
306 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
307 {
308 gphi *phi = psi.phi ();
309 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
310 tree arg = USE_FROM_PTR (use_p);
311
312 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
313 if (TREE_CODE (arg) != SSA_NAME
314 || SSA_NAME_IS_DEFAULT_DEF (arg)
315 || ! flow_bb_inside_loop_p (loop,
316 gimple_bb (SSA_NAME_DEF_STMT (arg))))
317 continue;
318
319 tree res = copy_ssa_name (arg);
320 gphi *close_phi = create_phi_node (res, close);
321 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
322 UNKNOWN_LOCATION);
323 SET_USE (use_p, res);
324 }
325 bb = close;
326 }
327
328 /* Eliminate duplicates. This relies on processing loops from
329 innermost to outer. */
330 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
331 {
332 gphi_iterator gsi = psi;
333 gphi *phi = psi.phi ();
334
335 /* At this point, PHI should be a close phi in normal form. */
336 gcc_assert (gimple_phi_num_args (phi) == 1);
337
338 /* Iterate over the next phis and remove duplicates. */
339 gsi_next (&gsi);
340 while (!gsi_end_p (gsi))
341 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0)
342 && may_propagate_copy (gimple_phi_result (gsi.phi ()),
343 gimple_phi_result (phi)))
344 {
345 replace_uses_by (gimple_phi_result (gsi.phi ()),
346 gimple_phi_result (phi));
347 remove_phi_node (&gsi, true);
348 }
349 else
350 gsi_next (&gsi);
351 }
352}
353
354/* Converts the current loop closed SSA form to a canonical form
355 expected by the Graphite code generation.
356
357 The loop closed SSA form has the following invariant: a variable
358 defined in a loop that is used outside the loop appears only in the
359 phi nodes in the destination of the loop exit. These phi nodes are
360 called close phi nodes.
361
362 The canonical loop closed SSA form contains the extra invariants:
363
364 - when the loop contains only one exit, the close phi nodes contain
365 only one argument. That implies that the basic block that contains
366 the close phi nodes has only one predecessor, that is a basic block
367 in the loop.
368
369 - the basic block containing the close phi nodes does not contain
370 other statements.
371
372 - there exist only one phi node per definition in the loop.
373
374 In addition to that we also make sure that loop exit edges are
375 first in the successor edge vector. This is to make RPO order
376 as computed by pre_and_rev_post_order_compute be consistent with
377 what initial schedule generation expects.
378*/
379
380static void
381canonicalize_loop_form (void)
382{
383 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
384 {
385 edge e = single_exit (loop);
386 if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE)))
387 continue;
388
389 canonicalize_loop_closed_ssa (loop, e);
390
391 /* If the exit is not first in the edge vector make it so. */
392 if (e != EDGE_SUCC (e->src, 0))
393 {
394 unsigned ei;
395 for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei)
396 ;
397 std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0));
398 }
399 }
400
401 /* We can end up releasing duplicate exit PHIs and also introduce
402 additional copies so the cached information isn't correct anymore. */
403 scev_reset ();
404
405 checking_verify_loop_closed_ssa (true);
406}
407
408isl_ctx *the_isl_ctx;
409
410/* Perform a set of linear transforms on the loops of the current
411 function. */
412
413void
414graphite_transform_loops (void)
415{
416 int i;
417 scop_p scop;
418 bool changed = false;
419 vec<scop_p> scops = vNULL;
420 isl_ctx *ctx;
421
422 /* If a function is parallel it was most probably already run through graphite
423 once. No need to run again. */
424 if (parallelized_function_p (cfun->decl))
425 return;
426
427 calculate_dominance_info (CDI_DOMINATORS);
428
429 /* We rely on post-dominators during merging of SESE regions so those
430 have to be meaningful. */
431 connect_infinite_loops_to_exit ();
432
433 ctx = isl_ctx_alloc ();
434 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
435 the_isl_ctx = ctx;
436
437 sort_sibling_loops (cfun);
438 canonicalize_loop_form ();
439
440 /* Print the loop structure. */
441 if (dump_file && (dump_flags & TDF_DETAILS))
442 {
443 print_loops (dump_file, 2);
444 print_loops (dump_file, 3);
445 }
446
447 seir_cache = new hash_map<sese_scev_hash, tree>;
448
449 calculate_dominance_info (CDI_POST_DOMINATORS);
450 build_scops (&scops);
451 free_dominance_info (CDI_POST_DOMINATORS);
452
453 /* Remove the fake exits before transform given they are not reflected
454 in loop structures we end up verifying. */
455 remove_fake_exit_edges ();
456
457 if (dump_file && (dump_flags & TDF_DETAILS))
458 {
459 print_graphite_statistics (dump_file, scops);
460 print_global_statistics (dump_file);
461 }
462
463 FOR_EACH_VEC_ELT (scops, i, scop)
464 if (dbg_cnt (graphite_scop))
465 {
466 scop->isl_context = ctx;
467 if (!build_poly_scop (scop))
468 continue;
469
470 if (!apply_poly_transforms (scop))
471 continue;
472
473 changed = true;
474 if (graphite_regenerate_ast_isl (scop)
475 && dump_enabled_p ())
476 {
477 dump_user_location_t loc = find_loop_location
478 (scops[i]->scop_info->region.entry->dest->loop_father);
479 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
480 "loop nest optimized\n");
481 }
482 }
483
484 delete seir_cache;
485 seir_cache = NULL;
486
487 if (changed)
488 {
489 mark_virtual_operands_for_renaming (cfun);
490 update_ssa (TODO_update_ssa);
491 checking_verify_ssa (true, true);
492 rewrite_into_loop_closed_ssa (NULL, 0);
493 scev_reset ();
494 checking_verify_loop_structure ();
495 }
496
497 if (dump_file && (dump_flags & TDF_DETAILS))
498 {
499 int num_no_dependency = 0;
500
501 for (auto loop : loops_list (cfun, 0))
502 if (loop->can_be_parallel)
503 num_no_dependency++;
504
505 fprintf (dump_file, "%d loops carried no dependency.\n",
506 num_no_dependency);
507 }
508
509 free_scops (scops);
510 the_isl_ctx = NULL;
511 isl_ctx_free (ctx);
512
513 if (changed)
514 {
515 /* FIXME: Graphite does not update profile meaningfully currently. */
516 cfun->cfg->full_profile = false;
517 cleanup_tree_cfg ();
518 profile_status_for_fn (cfun) = PROFILE_ABSENT;
519 release_recorded_exits (cfun);
520 tree_estimate_probability (false);
521 }
522}
523
524#else /* If isl is not available: #ifndef HAVE_isl. */
525
526static void
527graphite_transform_loops (void)
528{
529 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
530}
531
532#endif
533
534
535static unsigned int
536graphite_transforms (struct function *fun)
537{
538 if (number_of_loops (fn: fun) <= 1)
539 return 0;
540
541 graphite_transform_loops ();
542
543 return 0;
544}
545
546static bool
547gate_graphite_transforms (void)
548{
549 /* Enable -fgraphite pass if any one of the graphite optimization flags
550 is turned on. */
551 if (flag_graphite_identity
552 || flag_loop_parallelize_all
553 || flag_loop_nest_optimize)
554 flag_graphite = 1;
555
556 return flag_graphite != 0;
557}
558
559namespace {
560
561const pass_data pass_data_graphite =
562{
563 .type: GIMPLE_PASS, /* type */
564 .name: "graphite0", /* name */
565 .optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */
566 .tv_id: TV_GRAPHITE, /* tv_id */
567 .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
568 .properties_provided: 0, /* properties_provided */
569 .properties_destroyed: 0, /* properties_destroyed */
570 .todo_flags_start: 0, /* todo_flags_start */
571 .todo_flags_finish: 0, /* todo_flags_finish */
572};
573
574class pass_graphite : public gimple_opt_pass
575{
576public:
577 pass_graphite (gcc::context *ctxt)
578 : gimple_opt_pass (pass_data_graphite, ctxt)
579 {}
580
581 /* opt_pass methods: */
582 bool gate (function *) final override { return gate_graphite_transforms (); }
583
584}; // class pass_graphite
585
586} // anon namespace
587
588gimple_opt_pass *
589make_pass_graphite (gcc::context *ctxt)
590{
591 return new pass_graphite (ctxt);
592}
593
594namespace {
595
596const pass_data pass_data_graphite_transforms =
597{
598 .type: GIMPLE_PASS, /* type */
599 .name: "graphite", /* name */
600 .optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */
601 .tv_id: TV_GRAPHITE_TRANSFORMS, /* tv_id */
602 .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
603 .properties_provided: 0, /* properties_provided */
604 .properties_destroyed: 0, /* properties_destroyed */
605 .todo_flags_start: 0, /* todo_flags_start */
606 .todo_flags_finish: 0, /* todo_flags_finish */
607};
608
609class pass_graphite_transforms : public gimple_opt_pass
610{
611public:
612 pass_graphite_transforms (gcc::context *ctxt)
613 : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
614 {}
615
616 /* opt_pass methods: */
617 bool gate (function *) final override { return gate_graphite_transforms (); }
618 unsigned int execute (function *fun) final override
619 {
620 return graphite_transforms (fun);
621 }
622
623}; // class pass_graphite_transforms
624
625} // anon namespace
626
627gimple_opt_pass *
628make_pass_graphite_transforms (gcc::context *ctxt)
629{
630 return new pass_graphite_transforms (ctxt);
631}
632
633
634

source code of gcc/graphite.cc