gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006-2019 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 USES_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 "params.h"
  40 #include "pretty-print.h"
  41 #include "cfganal.h"
  42
  43 #ifdef HAVE_isl
  44 #include "cfghooks.h"
  45 #include "tree.h"
  46 #include "gimple.h"
  47 #include "ssa.h"
  48 #include "fold-const.h"
  49 #include "gimple-iterator.h"
  50 #include "tree-cfg.h"
  51 #include "tree-ssa-loop.h"
  52 #include "tree-data-ref.h"
  53 #include "tree-scalar-evolution.h"
  54 #include "dbgcnt.h"
  55 #include "tree-parloops.h"
  56 #include "tree-cfgcleanup.h"
  57 #include "tree-vectorizer.h"
  58 #include "tree-ssa-loop-manip.h"
  59 #include "tree-ssa.h"
  60 #include "tree-into-ssa.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 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   loop_p loop;
 381   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 382     {
 383       edge e = single_exit (loop);
 384       if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE)))
 385         continue;
 386
 387       canonicalize_loop_closed_ssa (loop, e);
 388
 389       /* If the exit is not first in the edge vector make it so.  */
 390       if (e != EDGE_SUCC (e->src, 0))
 391         {
 392           unsigned ei;
 393           for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei)
 394             ;
 395           std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0));
 396         }
 397     }
 398
 399   /* We can end up releasing duplicate exit PHIs and also introduce
 400      additional copies so the cached information isn't correct anymore.  */
 401   scev_reset ();
 402
 403   checking_verify_loop_closed_ssa (true);
 404 }
 405
 406 isl_ctx *the_isl_ctx;
 407
 408 /* Perform a set of linear transforms on the loops of the current
 409    function.  */
 410
 411 void
 412 graphite_transform_loops (void)
 413 {
 414   int i;
 415   scop_p scop;
 416   bool changed = false;
 417   vec<scop_p> scops = vNULL;
 418   isl_ctx *ctx;
 419
 420   /* If a function is parallel it was most probably already run through graphite
 421      once. No need to run again.  */
 422   if (parallelized_function_p (cfun->decl))
 423     return;
 424
 425   calculate_dominance_info (CDI_DOMINATORS);
 426
 427   /* We rely on post-dominators during merging of SESE regions so those
 428      have to be meaningful.  */
 429   connect_infinite_loops_to_exit ();
 430
 431   ctx = isl_ctx_alloc ();
 432   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 433   the_isl_ctx = ctx;
 434
 435   sort_sibling_loops (cfun);
 436   canonicalize_loop_form ();
 437
 438   /* Print the loop structure.  */
 439   if (dump_file && (dump_flags & TDF_DETAILS))
 440     {
 441       print_loops (dump_file, 2);
 442       print_loops (dump_file, 3);
 443     }
 444
 445   seir_cache = new hash_map<sese_scev_hash, tree>;
 446
 447   calculate_dominance_info (CDI_POST_DOMINATORS);
 448   build_scops (&scops);
 449   free_dominance_info (CDI_POST_DOMINATORS);
 450
 451   /* Remove the fake exits before transform given they are not reflected
 452      in loop structures we end up verifying.  */
 453   remove_fake_exit_edges ();
 454
 455   if (dump_file && (dump_flags & TDF_DETAILS))
 456     {
 457       print_graphite_statistics (dump_file, scops);
 458       print_global_statistics (dump_file);
 459     }
 460
 461   FOR_EACH_VEC_ELT (scops, i, scop)
 462     if (dbg_cnt (graphite_scop))
 463       {
 464         scop->isl_context = ctx;
 465         if (!build_poly_scop (scop))
 466           continue;
 467
 468         if (!apply_poly_transforms (scop))
 469           continue;
 470
 471         changed = true;
 472         if (graphite_regenerate_ast_isl (scop)
 473             && dump_enabled_p ())
 474           {
 475             dump_user_location_t loc = find_loop_location
 476               (scops[i]->scop_info->region.entry->dest->loop_father);
 477             dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
 478                              "loop nest optimized\n");
 479           }
 480       }
 481
 482   delete seir_cache;
 483   seir_cache = NULL;
 484
 485   if (changed)
 486     {
 487       mark_virtual_operands_for_renaming (cfun);
 488       update_ssa (TODO_update_ssa);
 489       checking_verify_ssa (true, true);
 490       rewrite_into_loop_closed_ssa (NULL, 0);
 491       scev_reset ();
 492       checking_verify_loop_structure ();
 493     }
 494
 495   if (dump_file && (dump_flags & TDF_DETAILS))
 496     {
 497       loop_p loop;
 498       int num_no_dependency = 0;
 499
 500       FOR_EACH_LOOP (loop, 0)
 501         if (loop->can_be_parallel)
 502           num_no_dependency++;
 503
 504       fprintf (dump_file, "%d loops carried no dependency.\n",
 505                num_no_dependency);
 506     }
 507
 508   free_scops (scops);
 509   the_isl_ctx = NULL;
 510   isl_ctx_free (ctx);
 511
 512   if (changed)
 513     {
 514       cleanup_tree_cfg ();
 515       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 516       release_recorded_exits (cfun);
 517       tree_estimate_probability (false);
 518     }
 519 }
 520
 521 #else /* If isl is not available: #ifndef HAVE_isl.  */
 522
 523 static void
 524 graphite_transform_loops (void)
 525 {
 526   sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 527 }
 528
 529 #endif
 530
 531
 532 static unsigned int
 533 graphite_transforms (struct function *fun)
 534 {
 535   if (number_of_loops (fun) <= 1)
 536     return 0;
 537
 538   graphite_transform_loops ();
 539
 540   return 0;
 541 }
 542
 543 static bool
 544 gate_graphite_transforms (void)
 545 {
 546   /* Enable -fgraphite pass if any one of the graphite optimization flags
 547      is turned on.  */
 548   if (flag_graphite_identity
 549       || flag_loop_parallelize_all
 550       || flag_loop_nest_optimize)
 551     flag_graphite = 1;
 552
 553   return flag_graphite != 0;
 554 }
 555
 556 namespace {
 557
 558 const pass_data pass_data_graphite =
 559 {
 560   GIMPLE_PASS, /* type */
 561   "graphite0", /* name */
 562   OPTGROUP_LOOP, /* optinfo_flags */
 563   TV_GRAPHITE, /* tv_id */
 564   ( PROP_cfg | PROP_ssa ), /* properties_required */
 565   0, /* properties_provided */
 566   0, /* properties_destroyed */
 567   0, /* todo_flags_start */
 568   0, /* todo_flags_finish */
 569 };
 570
 571 class pass_graphite : public gimple_opt_pass
 572 {
 573 public:
 574   pass_graphite (gcc::context *ctxt)
 575     : gimple_opt_pass (pass_data_graphite, ctxt)
 576   {}
 577
 578   /* opt_pass methods: */
 579   virtual bool gate (function *) { return gate_graphite_transforms (); }
 580
 581 }; // class pass_graphite
 582
 583 } // anon namespace
 584
 585 gimple_opt_pass *
 586 make_pass_graphite (gcc::context *ctxt)
 587 {
 588   return new pass_graphite (ctxt);
 589 }
 590
 591 namespace {
 592
 593 const pass_data pass_data_graphite_transforms =
 594 {
 595   GIMPLE_PASS, /* type */
 596   "graphite", /* name */
 597   OPTGROUP_LOOP, /* optinfo_flags */
 598   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 599   ( PROP_cfg | PROP_ssa ), /* properties_required */
 600   0, /* properties_provided */
 601   0, /* properties_destroyed */
 602   0, /* todo_flags_start */
 603   0, /* todo_flags_finish */
 604 };
 605
 606 class pass_graphite_transforms : public gimple_opt_pass
 607 {
 608 public:
 609   pass_graphite_transforms (gcc::context *ctxt)
 610     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 611   {}
 612
 613   /* opt_pass methods: */
 614   virtual bool gate (function *) { return gate_graphite_transforms (); }
 615   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 616
 617 }; // class pass_graphite_transforms
 618
 619 } // anon namespace
 620
 621 gimple_opt_pass *
 622 make_pass_graphite_transforms (gcc::context *ctxt)
 623 {
 624   return new pass_graphite_transforms (ctxt);
 625 }
 626
 627