gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006-2021 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 "graphite.h"
  61
  62 /* Print global statistics to FILE.  */
  63
  64 static void
  65 print_global_statistics (FILE* file)
  66 {
  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 ();
  75
  76   basic_block bb;
  77
  78   FOR_ALL_BB_FN (bb, cfun)
  79     {
  80       gimple_stmt_iterator psi;
  81
  82       n_bbs++;
  83       if (bb->count.initialized_p ())
  84         n_p_bbs += bb->count;
  85
  86       /* Ignore artificial surrounding loop.  */
  87       if (bb == bb->loop_father->header
  88           && bb->index != 0)
  89         {
  90           n_loops++;
  91           n_p_loops += bb->count;
  92         }
  93
  94       if (EDGE_COUNT (bb->succs) > 1)
  95         {
  96           n_conditions++;
  97           if (bb->count.initialized_p ())
  98             n_p_conditions += bb->count;
  99         }
 100
 101       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 102         {
 103           n_stmts++;
 104           if (bb->count.initialized_p ())
 105             n_p_stmts += bb->count;
 106         }
 107     }
 108
 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");
 124 }
 125
 126 /* Print statistics for SCOP to FILE.  */
 127
 128 static void
 129 print_graphite_scop_statistics (FILE* file, scop_p scop)
 130 {
 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 ();
 139
 140   basic_block bb;
 141
 142   FOR_ALL_BB_FN (bb, cfun)
 143     {
 144       gimple_stmt_iterator psi;
 145       loop_p loop = bb->loop_father;
 146
 147       if (!bb_in_sese_p (bb, scop->scop_info->region))
 148         continue;
 149
 150       n_bbs++;
 151       if (bb->count.initialized_p ())
 152         n_p_bbs += bb->count;
 153
 154       if (EDGE_COUNT (bb->succs) > 1)
 155         {
 156           n_conditions++;
 157           n_p_conditions += bb->count;
 158         }
 159
 160       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 161         {
 162           n_stmts++;
 163           n_p_stmts += bb->count;
 164         }
 165
 166       if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
 167         {
 168           n_loops++;
 169           n_p_loops += bb->count;
 170         }
 171     }
 172
 173   fprintf (file, "\nFunction Name: %s\n", current_function_name ());
 174
 175   edge scop_begin = scop->scop_info->region.entry;
 176   edge scop_end = scop->scop_info->region.exit;
 177
 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);
 182
 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");
 198 }
 199
 200 /* Print statistics for SCOPS to FILE.  */
 201
 202 static void
 203 print_graphite_statistics (FILE* file, vec<scop_p> scops)
 204 {
 205   int i;
 206   scop_p scop;
 207
 208   FOR_EACH_VEC_ELT (scops, i, scop)
 209     print_graphite_scop_statistics (file, scop);
 210 }
 211
 212 struct seir_cache_key
 213 {
 214   hashval_t hash;
 215   int entry_dest;
 216   int exit_src;
 217   int loop_num;
 218   tree expr;
 219 };
 220
 221 struct sese_scev_hash : typed_noop_remove <seir_cache_key>
 222 {
 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)
 228   {
 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));
 234   }
 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; }
 240 };
 241
 242 static hash_map<sese_scev_hash, tree> *seir_cache;
 243
 244 /* Same as scalar_evolution_in_region but caches results so we avoid
 245    re-computing evolutions during transform phase.  */
 246
 247 tree
 248 cached_scalar_evolution_in_region (const sese_l &region, loop_p loop,
 249                                    tree expr)
 250 {
 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 ();
 262
 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;
 268 }
 269
 270 /* Deletes all scops in SCOPS.  */
 271
 272 static void
 273 free_scops (vec<scop_p> scops)
 274 {
 275   int i;
 276   scop_p scop;
 277
 278   FOR_EACH_VEC_ELT (scops, i, scop)
 279     free_scop (scop);
 280
 281   scops.release ();
 282 }
 283
 284 /* Transforms LOOP to the canonical loop closed SSA form.  */
 285
 286 static void
 287 canonicalize_loop_closed_ssa (loop_p loop, edge e)
 288 {
 289   basic_block bb;
 290   gphi_iterator psi;
 291
 292   bb = e->dest;
 293
 294   /* Make the loop-close PHI node BB contain only PHIs and have a
 295      single predecessor.  */
 296   if (single_pred_p (bb))
 297     {
 298       e = split_block_after_labels (bb);
 299       bb = e->src;
 300     }
 301   else
 302     {
 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))
 306         {
 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);
 310
 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;
 317
 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);
 323         }
 324       bb = close;
 325     }
 326
 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))
 330     {
 331       gphi_iterator gsi = psi;
 332       gphi *phi = psi.phi ();
 333
 334       /* At this point, PHI should be a close phi in normal form.  */
 335       gcc_assert (gimple_phi_num_args (phi) == 1);
 336
 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))
 341           {
 342             replace_uses_by (gimple_phi_result (gsi.phi ()),
 343                              gimple_phi_result (phi));
 344             remove_phi_node (&gsi, true);
 345           }
 346         else
 347           gsi_next (&gsi);
 348     }
 349 }
 350
 351 /* Converts the current loop closed SSA form to a canonical form
 352    expected by the Graphite code generation.
 353
 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.
 358
 359    The canonical loop closed SSA form contains the extra invariants:
 360
 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.
 365
 366    - the basic block containing the close phi nodes does not contain
 367    other statements.
 368
 369    - there exist only one phi node per definition in the loop.
 370
 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.
 375 */
 376
 377 static void
 378 canonicalize_loop_form (void)
 379 {
 380   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
 381     {
 382       edge e = single_exit (loop);
 383       if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE)))
 384         continue;
 385
 386       canonicalize_loop_closed_ssa (loop, e);
 387
 388       /* If the exit is not first in the edge vector make it so.  */
 389       if (e != EDGE_SUCC (e->src, 0))
 390         {
 391           unsigned ei;
 392           for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei)
 393             ;
 394           std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0));
 395         }
 396     }
 397
 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 ();
 401
 402   checking_verify_loop_closed_ssa (true);
 403 }
 404
 405 isl_ctx *the_isl_ctx;
 406
 407 /* Perform a set of linear transforms on the loops of the current
 408    function.  */
 409
 410 void
 411 graphite_transform_loops (void)
 412 {
 413   int i;
 414   scop_p scop;
 415   bool changed = false;
 416   vec<scop_p> scops = vNULL;
 417   isl_ctx *ctx;
 418
 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;
 423
 424   calculate_dominance_info (CDI_DOMINATORS);
 425
 426   /* We rely on post-dominators during merging of SESE regions so those
 427      have to be meaningful.  */
 428   connect_infinite_loops_to_exit ();
 429
 430   ctx = isl_ctx_alloc ();
 431   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 432   the_isl_ctx = ctx;
 433
 434   sort_sibling_loops (cfun);
 435   canonicalize_loop_form ();
 436
 437   /* Print the loop structure.  */
 438   if (dump_file && (dump_flags & TDF_DETAILS))
 439     {
 440       print_loops (dump_file, 2);
 441       print_loops (dump_file, 3);
 442     }
 443
 444   seir_cache = new hash_map<sese_scev_hash, tree>;
 445
 446   calculate_dominance_info (CDI_POST_DOMINATORS);
 447   build_scops (&scops);
 448   free_dominance_info (CDI_POST_DOMINATORS);
 449
 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 ();
 453
 454   if (dump_file && (dump_flags & TDF_DETAILS))
 455     {
 456       print_graphite_statistics (dump_file, scops);
 457       print_global_statistics (dump_file);
 458     }
 459
 460   FOR_EACH_VEC_ELT (scops, i, scop)
 461     if (dbg_cnt (graphite_scop))
 462       {
 463         scop->isl_context = ctx;
 464         if (!build_poly_scop (scop))
 465           continue;
 466
 467         if (!apply_poly_transforms (scop))
 468           continue;
 469
 470         changed = true;
 471         if (graphite_regenerate_ast_isl (scop)
 472             && dump_enabled_p ())
 473           {
 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");
 478           }
 479       }
 480
 481   delete seir_cache;
 482   seir_cache = NULL;
 483
 484   if (changed)
 485     {
 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 ();
 492     }
 493
 494   if (dump_file && (dump_flags & TDF_DETAILS))
 495     {
 496       int num_no_dependency = 0;
 497
 498       for (auto loop : loops_list (cfun, 0))
 499         if (loop->can_be_parallel)
 500           num_no_dependency++;
 501
 502       fprintf (dump_file, "%d loops carried no dependency.\n",
 503                num_no_dependency);
 504     }
 505
 506   free_scops (scops);
 507   the_isl_ctx = NULL;
 508   isl_ctx_free (ctx);
 509
 510   if (changed)
 511     {
 512       cleanup_tree_cfg ();
 513       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 514       release_recorded_exits (cfun);
 515       tree_estimate_probability (false);
 516     }
 517 }
 518
 519 #else /* If isl is not available: #ifndef HAVE_isl.  */
 520
 521 static void
 522 graphite_transform_loops (void)
 523 {
 524   sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 525 }
 526
 527 #endif
 528
 529
 530 static unsigned int
 531 graphite_transforms (struct function *fun)
 532 {
 533   if (number_of_loops (fun) <= 1)
 534     return 0;
 535
 536   graphite_transform_loops ();
 537
 538   return 0;
 539 }
 540
 541 static bool
 542 gate_graphite_transforms (void)
 543 {
 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;
 550
 551   return flag_graphite != 0;
 552 }
 553
 554 namespace {
 555
 556 const pass_data pass_data_graphite =
 557 {
 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 */
 567 };
 568
 569 class pass_graphite : public gimple_opt_pass
 570 {
 571 public:
 572   pass_graphite (gcc::context *ctxt)
 573     : gimple_opt_pass (pass_data_graphite, ctxt)
 574   {}
 575
 576   /* opt_pass methods: */
 577   virtual bool gate (function *) { return gate_graphite_transforms (); }
 578
 579 }; // class pass_graphite
 580
 581 } // anon namespace
 582
 583 gimple_opt_pass *
 584 make_pass_graphite (gcc::context *ctxt)
 585 {
 586   return new pass_graphite (ctxt);
 587 }
 588
 589 namespace {
 590
 591 const pass_data pass_data_graphite_transforms =
 592 {
 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 */
 602 };
 603
 604 class pass_graphite_transforms : public gimple_opt_pass
 605 {
 606 public:
 607   pass_graphite_transforms (gcc::context *ctxt)
 608     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 609   {}
 610
 611   /* opt_pass methods: */
 612   virtual bool gate (function *) { return gate_graphite_transforms (); }
 613   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 614
 615 }; // class pass_graphite_transforms
 616
 617 } // anon namespace
 618
 619 gimple_opt_pass *
 620 make_pass_graphite_transforms (gcc::context *ctxt)
 621 {
 622   return new pass_graphite_transforms (ctxt);
 623 }
 624
 625