Line data Source code
1 : /* Gimple Represented as Polyhedra.
2 : Copyright (C) 2006-2026 Free Software Foundation, Inc.
3 : Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
4 :
5 : This file is part of GCC.
6 :
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.
11 :
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.
16 :
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/>. */
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 :
65 : static void
66 189 : print_global_statistics (FILE* file)
67 : {
68 189 : long n_bbs = 0;
69 189 : long n_loops = 0;
70 189 : long n_stmts = 0;
71 189 : long n_conditions = 0;
72 189 : profile_count n_p_bbs = profile_count::zero ();
73 189 : profile_count n_p_loops = profile_count::zero ();
74 189 : profile_count n_p_stmts = profile_count::zero ();
75 189 : profile_count n_p_conditions = profile_count::zero ();
76 :
77 189 : basic_block bb;
78 :
79 2983 : FOR_ALL_BB_FN (bb, cfun)
80 : {
81 2794 : gimple_stmt_iterator psi;
82 :
83 2794 : n_bbs++;
84 2794 : if (bb->count.initialized_p ())
85 2794 : n_p_bbs += bb->count;
86 :
87 : /* Ignore artificial surrounding loop. */
88 2794 : if (bb == bb->loop_father->header
89 633 : && bb->index != 0)
90 : {
91 444 : n_loops++;
92 444 : n_p_loops += bb->count;
93 : }
94 :
95 2794 : if (EDGE_COUNT (bb->succs) > 1)
96 : {
97 674 : n_conditions++;
98 674 : if (bb->count.initialized_p ())
99 674 : n_p_conditions += bb->count;
100 : }
101 :
102 9716 : for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
103 : {
104 4128 : n_stmts++;
105 4128 : if (bb->count.initialized_p ())
106 4128 : n_p_stmts += bb->count;
107 : }
108 : }
109 :
110 189 : fprintf (file, "\nGlobal statistics (");
111 189 : fprintf (file, "BBS:%ld, ", n_bbs);
112 189 : fprintf (file, "LOOPS:%ld, ", n_loops);
113 189 : fprintf (file, "CONDITIONS:%ld, ", n_conditions);
114 189 : fprintf (file, "STMTS:%ld)\n", n_stmts);
115 189 : fprintf (file, "Global profiling statistics (");
116 189 : fprintf (file, "BBS:");
117 189 : n_p_bbs.dump (file);
118 189 : fprintf (file, ", LOOPS:");
119 189 : n_p_loops.dump (file);
120 189 : fprintf (file, ", CONDITIONS:");
121 189 : n_p_conditions.dump (file);
122 189 : fprintf (file, ", STMTS:");
123 189 : n_p_stmts.dump (file);
124 189 : fprintf (file, ")\n\n");
125 189 : }
126 :
127 : /* Print statistics for SCOP to FILE. */
128 :
129 : static void
130 100 : print_graphite_scop_statistics (FILE* file, scop_p scop)
131 : {
132 100 : long n_bbs = 0;
133 100 : long n_loops = 0;
134 100 : long n_stmts = 0;
135 100 : long n_conditions = 0;
136 100 : profile_count n_p_bbs = profile_count::zero ();
137 100 : profile_count n_p_loops = profile_count::zero ();
138 100 : profile_count n_p_stmts = profile_count::zero ();
139 100 : profile_count n_p_conditions = profile_count::zero ();
140 :
141 100 : basic_block bb;
142 :
143 2013 : FOR_ALL_BB_FN (bb, cfun)
144 : {
145 1913 : gimple_stmt_iterator psi;
146 1913 : loop_p loop = bb->loop_father;
147 :
148 1913 : if (!bb_in_sese_p (bb, scop->scop_info->region))
149 837 : continue;
150 :
151 1076 : n_bbs++;
152 1076 : if (bb->count.initialized_p ())
153 1076 : n_p_bbs += bb->count;
154 :
155 1076 : if (EDGE_COUNT (bb->succs) > 1)
156 : {
157 304 : n_conditions++;
158 304 : n_p_conditions += bb->count;
159 : }
160 :
161 3795 : for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
162 : {
163 1643 : n_stmts++;
164 1643 : n_p_stmts += bb->count;
165 : }
166 :
167 1076 : if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
168 : {
169 278 : n_loops++;
170 278 : n_p_loops += bb->count;
171 : }
172 : }
173 :
174 100 : fprintf (file, "\nFunction Name: %s\n", current_function_name ());
175 :
176 100 : edge scop_begin = scop->scop_info->region.entry;
177 100 : edge scop_end = scop->scop_info->region.exit;
178 :
179 100 : fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
180 100 : scop_begin->src->index, scop_begin->dest->index);
181 100 : fprintf (file, "exit_edge (bb_%d, bb_%d))",
182 100 : scop_end->src->index, scop_end->dest->index);
183 :
184 100 : fprintf (file, "\nSCoP statistics (");
185 100 : fprintf (file, "BBS:%ld, ", n_bbs);
186 100 : fprintf (file, "LOOPS:%ld, ", n_loops);
187 100 : fprintf (file, "CONDITIONS:%ld, ", n_conditions);
188 100 : fprintf (file, "STMTS:%ld)\n", n_stmts);
189 100 : fprintf (file, "SCoP profiling statistics (");
190 100 : fprintf (file, "BBS:");
191 100 : n_p_bbs.dump (file);
192 100 : fprintf (file, ", LOOPS:");
193 100 : n_p_loops.dump (file);
194 100 : fprintf (file, ", CONDITIONS:");
195 100 : n_p_conditions.dump (file);
196 100 : fprintf (file, ", STMTS:");
197 100 : n_p_stmts.dump (file);
198 100 : fprintf (file, ")\n\n");
199 100 : }
200 :
201 : /* Print statistics for SCOPS to FILE. */
202 :
203 : static void
204 189 : print_graphite_statistics (FILE* file, vec<scop_p> scops)
205 : {
206 189 : int i;
207 189 : scop_p scop;
208 :
209 289 : FOR_EACH_VEC_ELT (scops, i, scop)
210 100 : print_graphite_scop_statistics (file, scop);
211 189 : }
212 :
213 : struct 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 :
222 : struct 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 51722 : static hashval_t hash (const seir_cache_key &key) { return key.hash; }
227 : static bool
228 45120 : equal (const seir_cache_key &key1, const seir_cache_key &key2)
229 : {
230 45120 : return (key1.hash == key2.hash
231 1733 : && key1.entry_dest == key2.entry_dest
232 1733 : && key1.exit_src == key2.exit_src
233 1733 : && key1.loop_num == key2.loop_num
234 46853 : && 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 23781 : static void mark_empty (seir_cache_key &key) { key.entry_dest = 0; }
239 7222 : static bool is_deleted (const seir_cache_key &key) { return !key.expr; }
240 220048 : static bool is_empty (const seir_cache_key &key) { return key.entry_dest == 0; }
241 : };
242 :
243 : static 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 :
248 : tree
249 8910 : cached_scalar_evolution_in_region (const sese_l ®ion, loop_p loop,
250 : tree expr)
251 : {
252 8910 : seir_cache_key key;
253 8910 : key.entry_dest = region.entry->dest->index;
254 8910 : key.exit_src = region.exit->src->index;
255 8910 : key.loop_num = loop->num;
256 8910 : key.expr = expr;
257 8910 : inchash::hash hstate (0);
258 8910 : hstate.add_int (key.entry_dest);
259 8910 : hstate.add_int (key.exit_src);
260 8910 : hstate.add_int (key.loop_num);
261 8910 : inchash::add_expr (key.expr, hstate);
262 8910 : key.hash = hstate.end ();
263 :
264 8910 : bool existed;
265 8910 : tree &chrec = seir_cache->get_or_insert (key, &existed);
266 8910 : if (!existed)
267 7222 : chrec = scalar_evolution_in_region (region, loop, expr);
268 8910 : return chrec;
269 : }
270 :
271 : /* Deletes all scops in SCOPS. */
272 :
273 : static void
274 556 : free_scops (vec<scop_p> scops)
275 : {
276 556 : int i;
277 556 : scop_p scop;
278 :
279 757 : FOR_EACH_VEC_ELT (scops, i, scop)
280 201 : free_scop (scop);
281 :
282 556 : scops.release ();
283 556 : }
284 :
285 : /* Transforms LOOP to the canonical loop closed SSA form. */
286 :
287 : static void
288 1159 : canonicalize_loop_closed_ssa (loop_p loop, edge e)
289 : {
290 1159 : basic_block bb;
291 1159 : gphi_iterator psi;
292 :
293 1159 : bb = e->dest;
294 :
295 : /* Make the loop-close PHI node BB contain only PHIs and have a
296 : single predecessor. */
297 1159 : if (single_pred_p (bb))
298 : {
299 1056 : e = split_block_after_labels (bb);
300 1056 : bb = e->src;
301 : }
302 : else
303 : {
304 103 : basic_block close = split_edge (e);
305 103 : e = single_succ_edge (close);
306 289 : for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
307 : {
308 186 : gphi *phi = psi.phi ();
309 186 : use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
310 186 : tree arg = USE_FROM_PTR (use_p);
311 :
312 : /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
313 225 : if (TREE_CODE (arg) != SSA_NAME
314 164 : || SSA_NAME_IS_DEFAULT_DEF (arg)
315 349 : || ! flow_bb_inside_loop_p (loop,
316 163 : gimple_bb (SSA_NAME_DEF_STMT (arg))))
317 39 : continue;
318 :
319 147 : tree res = copy_ssa_name (arg);
320 147 : gphi *close_phi = create_phi_node (res, close);
321 147 : add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
322 : UNKNOWN_LOCATION);
323 147 : 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 2525 : for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
331 : {
332 1366 : gphi_iterator gsi = psi;
333 1366 : gphi *phi = psi.phi ();
334 :
335 : /* At this point, PHI should be a close phi in normal form. */
336 1366 : gcc_assert (gimple_phi_num_args (phi) == 1);
337 :
338 : /* Iterate over the next phis and remove duplicates. */
339 1366 : gsi_next (&gsi);
340 1803 : while (!gsi_end_p (gsi))
341 437 : if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0)
342 437 : && may_propagate_copy (gimple_phi_result (gsi.phi ()),
343 : gimple_phi_result (phi)))
344 : {
345 2 : replace_uses_by (gimple_phi_result (gsi.phi ()),
346 : gimple_phi_result (phi));
347 2 : remove_phi_node (&gsi, true);
348 : }
349 : else
350 435 : gsi_next (&gsi);
351 : }
352 1159 : }
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 :
380 : static void
381 556 : canonicalize_loop_form (void)
382 : {
383 3041 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
384 : {
385 1373 : edge e = single_exit (loop);
386 1373 : if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE)))
387 214 : continue;
388 :
389 1159 : canonicalize_loop_closed_ssa (loop, e);
390 :
391 : /* If the exit is not first in the edge vector make it so. */
392 1159 : if (e != EDGE_SUCC (e->src, 0))
393 : {
394 : unsigned ei;
395 1498 : for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei)
396 : ;
397 749 : std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0));
398 : }
399 556 : }
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 556 : scev_reset ();
404 :
405 556 : checking_verify_loop_closed_ssa (true);
406 556 : }
407 :
408 : isl_ctx *the_isl_ctx;
409 :
410 : /* Perform a set of linear transforms on the loops of the current
411 : function. */
412 :
413 : void
414 603 : graphite_transform_loops (void)
415 : {
416 603 : int i;
417 603 : scop_p scop;
418 603 : bool changed = false;
419 603 : vec<scop_p> scops = vNULL;
420 603 : 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 603 : if (parallelized_function_p (cfun->decl))
425 47 : return;
426 :
427 556 : 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 556 : connect_infinite_loops_to_exit ();
432 :
433 556 : ctx = isl_ctx_alloc ();
434 556 : isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
435 556 : the_isl_ctx = ctx;
436 :
437 556 : sort_sibling_loops (cfun);
438 556 : canonicalize_loop_form ();
439 :
440 : /* Print the loop structure. */
441 556 : if (dump_file && (dump_flags & TDF_DETAILS))
442 : {
443 189 : print_loops (dump_file, 2);
444 189 : print_loops (dump_file, 3);
445 : }
446 :
447 556 : seir_cache = new hash_map<sese_scev_hash, tree>;
448 :
449 556 : calculate_dominance_info (CDI_POST_DOMINATORS);
450 556 : build_scops (&scops);
451 556 : 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 556 : remove_fake_exit_edges ();
456 :
457 556 : if (dump_file && (dump_flags & TDF_DETAILS))
458 : {
459 189 : print_graphite_statistics (dump_file, scops);
460 189 : print_global_statistics (dump_file);
461 : }
462 :
463 757 : FOR_EACH_VEC_ELT (scops, i, scop)
464 201 : if (dbg_cnt (graphite_scop))
465 : {
466 201 : scop->isl_context = ctx;
467 201 : if (!build_poly_scop (scop))
468 0 : continue;
469 :
470 201 : if (!apply_poly_transforms (scop))
471 38 : continue;
472 :
473 163 : changed = true;
474 163 : if (graphite_regenerate_ast_isl (scop)
475 163 : && dump_enabled_p ())
476 : {
477 71 : dump_user_location_t loc = find_loop_location
478 71 : (scops[i]->scop_info->region.entry->dest->loop_father);
479 71 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
480 : "loop nest optimized\n");
481 : }
482 : }
483 :
484 1112 : delete seir_cache;
485 556 : seir_cache = NULL;
486 :
487 556 : if (changed)
488 : {
489 152 : mark_virtual_operands_for_renaming (cfun);
490 152 : update_ssa (TODO_update_ssa);
491 152 : checking_verify_ssa (true, true);
492 152 : rewrite_into_loop_closed_ssa (NULL, 0);
493 152 : scev_reset ();
494 152 : checking_verify_loop_structure ();
495 : }
496 :
497 556 : if (dump_file && (dump_flags & TDF_DETAILS))
498 : {
499 189 : int num_no_dependency = 0;
500 :
501 1245 : for (auto loop : loops_list (cfun, 0))
502 678 : if (loop->can_be_parallel)
503 26 : num_no_dependency++;
504 :
505 189 : fprintf (dump_file, "%d loops carried no dependency.\n",
506 : num_no_dependency);
507 : }
508 :
509 556 : free_scops (scops);
510 556 : the_isl_ctx = NULL;
511 556 : isl_ctx_free (ctx);
512 :
513 556 : if (changed)
514 : {
515 : /* FIXME: Graphite does not update profile meaningfully currently. */
516 152 : cfun->cfg->full_profile = false;
517 152 : cleanup_tree_cfg ();
518 152 : profile_status_for_fn (cfun) = PROFILE_ABSENT;
519 152 : release_recorded_exits (cfun);
520 152 : tree_estimate_probability (false);
521 : }
522 : }
523 :
524 : #else /* If isl is not available: #ifndef HAVE_isl. */
525 :
526 : static void
527 : graphite_transform_loops (void)
528 : {
529 : sorry ("Graphite loop optimizations cannot be used (isl is not available).");
530 : }
531 :
532 : #endif
533 :
534 :
535 : static unsigned int
536 603 : graphite_transforms (struct function *fun)
537 : {
538 1206 : if (number_of_loops (fun) <= 1)
539 : return 0;
540 :
541 603 : graphite_transform_loops ();
542 :
543 603 : return 0;
544 : }
545 :
546 : static bool
547 242066 : gate_graphite_transforms (void)
548 : {
549 : /* Enable -fgraphite pass if any one of the graphite optimization flags
550 : is turned on. */
551 242066 : if (flag_graphite_identity
552 241690 : || flag_loop_parallelize_all
553 241476 : || flag_loop_nest_optimize)
554 1128 : flag_graphite = 1;
555 :
556 242066 : return flag_graphite != 0;
557 : }
558 :
559 : namespace {
560 :
561 : const pass_data pass_data_graphite =
562 : {
563 : GIMPLE_PASS, /* type */
564 : "graphite0", /* name */
565 : OPTGROUP_LOOP, /* optinfo_flags */
566 : TV_GRAPHITE, /* tv_id */
567 : ( PROP_cfg | PROP_ssa ), /* properties_required */
568 : 0, /* properties_provided */
569 : 0, /* properties_destroyed */
570 : 0, /* todo_flags_start */
571 : 0, /* todo_flags_finish */
572 : };
573 :
574 : class pass_graphite : public gimple_opt_pass
575 : {
576 : public:
577 285722 : pass_graphite (gcc::context *ctxt)
578 571444 : : gimple_opt_pass (pass_data_graphite, ctxt)
579 : {}
580 :
581 : /* opt_pass methods: */
582 241458 : bool gate (function *) final override { return gate_graphite_transforms (); }
583 :
584 : }; // class pass_graphite
585 :
586 : } // anon namespace
587 :
588 : gimple_opt_pass *
589 285722 : make_pass_graphite (gcc::context *ctxt)
590 : {
591 285722 : return new pass_graphite (ctxt);
592 : }
593 :
594 : namespace {
595 :
596 : const pass_data pass_data_graphite_transforms =
597 : {
598 : GIMPLE_PASS, /* type */
599 : "graphite", /* name */
600 : OPTGROUP_LOOP, /* optinfo_flags */
601 : TV_GRAPHITE_TRANSFORMS, /* tv_id */
602 : ( PROP_cfg | PROP_ssa ), /* properties_required */
603 : 0, /* properties_provided */
604 : 0, /* properties_destroyed */
605 : 0, /* todo_flags_start */
606 : 0, /* todo_flags_finish */
607 : };
608 :
609 : class pass_graphite_transforms : public gimple_opt_pass
610 : {
611 : public:
612 285722 : pass_graphite_transforms (gcc::context *ctxt)
613 571444 : : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
614 : {}
615 :
616 : /* opt_pass methods: */
617 608 : bool gate (function *) final override { return gate_graphite_transforms (); }
618 603 : unsigned int execute (function *fun) final override
619 : {
620 603 : return graphite_transforms (fun);
621 : }
622 :
623 : }; // class pass_graphite_transforms
624 :
625 : } // anon namespace
626 :
627 : gimple_opt_pass *
628 285722 : make_pass_graphite_transforms (gcc::context *ctxt)
629 : {
630 285722 : return new pass_graphite_transforms (ctxt);
631 : }
632 :
633 :
|
