gcc/graphite.cc

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006-2023 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 print_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
 129 static void
 130 print_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
 203 static void
 204 print_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
 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   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
 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 cached_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
 273 static void
 274 free_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
 287 static void
 288 canonicalize_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
 380 static void
 381 canonicalize_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
 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 graphite_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       cleanup_tree_cfg ();
 516       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 517       release_recorded_exits (cfun);
 518       tree_estimate_probability (false);
 519     }
 520 }
 521
 522 #else /* If isl is not available: #ifndef HAVE_isl.  */
 523
 524 static void
 525 graphite_transform_loops (void)
 526 {
 527   sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 528 }
 529
 530 #endif
 531
 532
 533 static unsigned int
 534 graphite_transforms (struct function *fun)
 535 {
 536   if (number_of_loops (fun) <= 1)
 537     return 0;
 538
 539   graphite_transform_loops ();
 540
 541   return 0;
 542 }
 543
 544 static bool
 545 gate_graphite_transforms (void)
 546 {
 547   /* Enable -fgraphite pass if any one of the graphite optimization flags
 548      is turned on.  */
 549   if (flag_graphite_identity
 550       || flag_loop_parallelize_all
 551       || flag_loop_nest_optimize)
 552     flag_graphite = 1;
 553
 554   return flag_graphite != 0;
 555 }
 556
 557 namespace {
 558
 559 const pass_data pass_data_graphite =
 560 {
 561   GIMPLE_PASS, /* type */
 562   "graphite0", /* name */
 563   OPTGROUP_LOOP, /* optinfo_flags */
 564   TV_GRAPHITE, /* tv_id */
 565   ( PROP_cfg | PROP_ssa ), /* properties_required */
 566   0, /* properties_provided */
 567   0, /* properties_destroyed */
 568   0, /* todo_flags_start */
 569   0, /* todo_flags_finish */
 570 };
 571
 572 class pass_graphite : public gimple_opt_pass
 573 {
 574 public:
 575   pass_graphite (gcc::context *ctxt)
 576     : gimple_opt_pass (pass_data_graphite, ctxt)
 577   {}
 578
 579   /* opt_pass methods: */
 580   bool gate (function *) final override { return gate_graphite_transforms (); }
 581
 582 }; // class pass_graphite
 583
 584 } // anon namespace
 585
 586 gimple_opt_pass *
 587 make_pass_graphite (gcc::context *ctxt)
 588 {
 589   return new pass_graphite (ctxt);
 590 }
 591
 592 namespace {
 593
 594 const pass_data pass_data_graphite_transforms =
 595 {
 596   GIMPLE_PASS, /* type */
 597   "graphite", /* name */
 598   OPTGROUP_LOOP, /* optinfo_flags */
 599   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 600   ( PROP_cfg | PROP_ssa ), /* properties_required */
 601   0, /* properties_provided */
 602   0, /* properties_destroyed */
 603   0, /* todo_flags_start */
 604   0, /* todo_flags_finish */
 605 };
 606
 607 class pass_graphite_transforms : public gimple_opt_pass
 608 {
 609 public:
 610   pass_graphite_transforms (gcc::context *ctxt)
 611     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 612   {}
 613
 614   /* opt_pass methods: */
 615   bool gate (function *) final override { return gate_graphite_transforms (); }
 616   unsigned int execute (function *fun) final override
 617   {
 618     return graphite_transforms (fun);
 619   }
 620
 621 }; // class pass_graphite_transforms
 622
 623 } // anon namespace
 624
 625 gimple_opt_pass *
 626 make_pass_graphite_transforms (gcc::context *ctxt)
 627 {
 628   return new pass_graphite_transforms (ctxt);
 629 }
 630
 631