gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006-2017 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
  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 "graphite.h"
  59
  60 /* Print global statistics to FILE.  */
  61
  62 static void
  63 print_global_statistics (FILE* file)
  64 {
  65   long n_bbs = 0;
  66   long n_loops = 0;
  67   long n_stmts = 0;
  68   long n_conditions = 0;
  69   profile_count n_p_bbs = profile_count::zero ();
  70   profile_count n_p_loops = profile_count::zero ();
  71   profile_count n_p_stmts = profile_count::zero ();
  72   profile_count n_p_conditions = profile_count::zero ();
  73
  74   basic_block bb;
  75
  76   FOR_ALL_BB_FN (bb, cfun)
  77     {
  78       gimple_stmt_iterator psi;
  79
  80       n_bbs++;
  81       if (bb->count.initialized_p ())
  82         n_p_bbs += bb->count;
  83
  84       /* Ignore artificial surrounding loop.  */
  85       if (bb == bb->loop_father->header
  86           && bb->index != 0)
  87         {
  88           n_loops++;
  89           n_p_loops += bb->count;
  90         }
  91
  92       if (EDGE_COUNT (bb->succs) > 1)
  93         {
  94           n_conditions++;
  95           if (bb->count.initialized_p ())
  96             n_p_conditions += bb->count;
  97         }
  98
  99       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 100         {
 101           n_stmts++;
 102           if (bb->count.initialized_p ())
 103             n_p_stmts += bb->count;
 104         }
 105     }
 106
 107   fprintf (file, "\nGlobal statistics (");
 108   fprintf (file, "BBS:%ld, ", n_bbs);
 109   fprintf (file, "LOOPS:%ld, ", n_loops);
 110   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 111   fprintf (file, "STMTS:%ld)\n", n_stmts);
 112   fprintf (file, "\nGlobal profiling statistics (");
 113   fprintf (file, "BBS:");
 114   n_p_bbs.dump (file);
 115   fprintf (file, ", LOOPS:");
 116   n_p_loops.dump (file);
 117   fprintf (file, ", CONDITIONS:");
 118   n_p_conditions.dump (file);
 119   fprintf (file, ", STMTS:");
 120   n_p_stmts.dump (file);
 121   fprintf (file, ")\n");
 122 }
 123
 124 /* Print statistics for SCOP to FILE.  */
 125
 126 static void
 127 print_graphite_scop_statistics (FILE* file, scop_p scop)
 128 {
 129   long n_bbs = 0;
 130   long n_loops = 0;
 131   long n_stmts = 0;
 132   long n_conditions = 0;
 133   profile_count n_p_bbs = profile_count::zero ();
 134   profile_count n_p_loops = profile_count::zero ();
 135   profile_count n_p_stmts = profile_count::zero ();
 136   profile_count n_p_conditions = profile_count::zero ();
 137
 138   basic_block bb;
 139
 140   FOR_ALL_BB_FN (bb, cfun)
 141     {
 142       gimple_stmt_iterator psi;
 143       loop_p loop = bb->loop_father;
 144
 145       if (!bb_in_sese_p (bb, scop->scop_info->region))
 146         continue;
 147
 148       n_bbs++;
 149       if (bb->count.initialized_p ())
 150         n_p_bbs += bb->count;
 151
 152       if (EDGE_COUNT (bb->succs) > 1)
 153         {
 154           n_conditions++;
 155           n_p_conditions += bb->count;
 156         }
 157
 158       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 159         {
 160           n_stmts++;
 161           n_p_stmts += bb->count;
 162         }
 163
 164       if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
 165         {
 166           n_loops++;
 167           n_p_loops += bb->count;
 168         }
 169     }
 170
 171   fprintf (file, "\nFunction Name: %s\n", current_function_name ());
 172
 173   edge scop_begin = scop->scop_info->region.entry;
 174   edge scop_end = scop->scop_info->region.exit;
 175
 176   fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
 177            scop_begin->src->index, scop_begin->dest->index);
 178   fprintf (file, "exit_edge (bb_%d, bb_%d))",
 179            scop_end->src->index, scop_end->dest->index);
 180
 181   fprintf (file, "\nSCoP statistics (");
 182   fprintf (file, "BBS:%ld, ", n_bbs);
 183   fprintf (file, "LOOPS:%ld, ", n_loops);
 184   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 185   fprintf (file, "STMTS:%ld)\n", n_stmts);
 186   fprintf (file, "\nSCoP profiling statistics (");
 187   fprintf (file, "BBS:");
 188   n_p_bbs.dump (file);
 189   fprintf (file, ", LOOPS:");
 190   n_p_loops.dump (file);
 191   fprintf (file, ", CONDITIONS:");
 192   n_p_conditions.dump (file);
 193   fprintf (file, ", STMTS:");
 194   n_p_stmts.dump (file);
 195   fprintf (file, ")\n");
 196 }
 197
 198 /* Print statistics for SCOPS to FILE.  */
 199
 200 static void
 201 print_graphite_statistics (FILE* file, vec<scop_p> scops)
 202 {
 203   int i;
 204
 205   scop_p scop;
 206
 207   FOR_EACH_VEC_ELT (scops, i, scop)
 208     print_graphite_scop_statistics (file, scop);
 209
 210   /* Print the loop structure.  */
 211   print_loops (file, 2);
 212   print_loops (file, 3);
 213 }
 214
 215 /* Initialize graphite: when there are no loops returns false.  */
 216
 217 static bool
 218 graphite_initialize (void)
 219 {
 220   int min_loops = PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION);
 221   int max_bbs = PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION);
 222   int nbbs = n_basic_blocks_for_fn (cfun);
 223   int nloops = number_of_loops (cfun);
 224
 225   if (nloops <= min_loops
 226       /* FIXME: This limit on the number of basic blocks of a function
 227          should be removed when the SCOP detection is faster.  */
 228       || (nbbs > max_bbs))
 229     {
 230       if (dump_file && (dump_flags & TDF_DETAILS))
 231         {
 232           if (nloops <= min_loops)
 233             fprintf (dump_file, "\nFunction does not have enough loops: "
 234                      "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n",
 235                      min_loops);
 236
 237           else if (nbbs > max_bbs)
 238             fprintf (dump_file, "\nFunction has too many basic blocks: "
 239                      "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs);
 240
 241           fprintf (dump_file, "\nnumber of SCoPs: 0\n");
 242           print_global_statistics (dump_file);
 243         }
 244
 245       return false;
 246     }
 247
 248   calculate_dominance_info (CDI_DOMINATORS);
 249   initialize_original_copy_tables ();
 250
 251   if (dump_file && dump_flags)
 252     {
 253       dump_function_to_file (current_function_decl, dump_file, dump_flags);
 254       print_loops (dump_file, 3);
 255     }
 256
 257   return true;
 258 }
 259
 260 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
 261    true.  */
 262
 263 static void
 264 graphite_finalize (bool need_cfg_cleanup_p)
 265 {
 266   if (need_cfg_cleanup_p)
 267     {
 268       free_dominance_info (CDI_DOMINATORS);
 269       scev_reset ();
 270       cleanup_tree_cfg ();
 271       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 272       release_recorded_exits (cfun);
 273       tree_estimate_probability (false);
 274     }
 275
 276   free_original_copy_tables ();
 277
 278   if (dump_file && dump_flags)
 279     print_loops (dump_file, 3);
 280 }
 281
 282 /* Deletes all scops in SCOPS.  */
 283
 284 static void
 285 free_scops (vec<scop_p> scops)
 286 {
 287   int i;
 288   scop_p scop;
 289
 290   FOR_EACH_VEC_ELT (scops, i, scop)
 291     free_scop (scop);
 292
 293   scops.release ();
 294 }
 295
 296 /* Transforms LOOP to the canonical loop closed SSA form.  */
 297
 298 static void
 299 canonicalize_loop_closed_ssa (loop_p loop)
 300 {
 301   edge e = single_exit (loop);
 302   basic_block bb;
 303   gphi_iterator psi;
 304
 305   if (!e || (e->flags & EDGE_COMPLEX))
 306     return;
 307
 308   bb = e->dest;
 309
 310   /* Make the loop-close PHI node BB contain only PHIs and have a
 311      single predecessor.  */
 312   if (single_pred_p (bb))
 313     {
 314       e = split_block_after_labels (bb);
 315       bb = e->src;
 316     }
 317   else
 318     {
 319       basic_block close = split_edge (e);
 320       e = single_succ_edge (close);
 321       for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 322         {
 323           gphi *phi = psi.phi ();
 324           use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
 325           tree arg = USE_FROM_PTR (use_p);
 326
 327           /* Only add close phi nodes for SSA_NAMEs defined in LOOP.  */
 328           if (TREE_CODE (arg) != SSA_NAME
 329               || loop_containing_stmt (SSA_NAME_DEF_STMT (arg)) != loop)
 330             continue;
 331
 332           tree res = copy_ssa_name (arg);
 333           gphi *close_phi = create_phi_node (res, close);
 334           add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
 335                        UNKNOWN_LOCATION);
 336           SET_USE (use_p, res);
 337         }
 338       bb = close;
 339     }
 340
 341   /* Eliminate duplicates.  This relies on processing loops from
 342      innermost to outer.  */
 343   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 344     {
 345       gphi_iterator gsi = psi;
 346       gphi *phi = psi.phi ();
 347
 348       /* At this point, PHI should be a close phi in normal form.  */
 349       gcc_assert (gimple_phi_num_args (phi) == 1);
 350
 351       /* Iterate over the next phis and remove duplicates.  */
 352       gsi_next (&gsi);
 353       while (!gsi_end_p (gsi))
 354         if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0))
 355           {
 356             replace_uses_by (gimple_phi_result (gsi.phi ()),
 357                              gimple_phi_result (phi));
 358             remove_phi_node (&gsi, true);
 359           }
 360         else
 361           gsi_next (&gsi);
 362     }
 363 }
 364
 365 /* Converts the current loop closed SSA form to a canonical form
 366    expected by the Graphite code generation.
 367
 368    The loop closed SSA form has the following invariant: a variable
 369    defined in a loop that is used outside the loop appears only in the
 370    phi nodes in the destination of the loop exit.  These phi nodes are
 371    called close phi nodes.
 372
 373    The canonical loop closed SSA form contains the extra invariants:
 374
 375    - when the loop contains only one exit, the close phi nodes contain
 376    only one argument.  That implies that the basic block that contains
 377    the close phi nodes has only one predecessor, that is a basic block
 378    in the loop.
 379
 380    - the basic block containing the close phi nodes does not contain
 381    other statements.
 382
 383    - there exist only one phi node per definition in the loop.
 384 */
 385
 386 static void
 387 canonicalize_loop_closed_ssa_form (void)
 388 {
 389   loop_p loop;
 390   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 391     canonicalize_loop_closed_ssa (loop);
 392
 393   checking_verify_loop_closed_ssa (true);
 394 }
 395
 396 isl_ctx *the_isl_ctx;
 397
 398 /* Perform a set of linear transforms on the loops of the current
 399    function.  */
 400
 401 void
 402 graphite_transform_loops (void)
 403 {
 404   int i;
 405   scop_p scop;
 406   bool need_cfg_cleanup_p = false;
 407   vec<scop_p> scops = vNULL;
 408   isl_ctx *ctx;
 409
 410   /* If a function is parallel it was most probably already run through graphite
 411      once. No need to run again.  */
 412   if (parallelized_function_p (cfun->decl))
 413     return;
 414
 415   if (!graphite_initialize ())
 416     return;
 417
 418   ctx = isl_ctx_alloc ();
 419   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 420   the_isl_ctx = ctx;
 421
 422   canonicalize_loop_closed_ssa_form ();
 423
 424   calculate_dominance_info (CDI_POST_DOMINATORS);
 425   build_scops (&scops);
 426   free_dominance_info (CDI_POST_DOMINATORS);
 427
 428   if (dump_file && (dump_flags & TDF_DETAILS))
 429     {
 430       print_graphite_statistics (dump_file, scops);
 431       print_global_statistics (dump_file);
 432     }
 433
 434   FOR_EACH_VEC_ELT (scops, i, scop)
 435     if (dbg_cnt (graphite_scop))
 436       {
 437         scop->isl_context = ctx;
 438         if (!build_poly_scop (scop))
 439           continue;
 440
 441         if (!apply_poly_transforms (scop))
 442           continue;
 443
 444         location_t loc = find_loop_location
 445           (scops[i]->scop_info->region.entry->dest->loop_father);
 446
 447         need_cfg_cleanup_p = true;
 448         if (!graphite_regenerate_ast_isl (scop))
 449           dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
 450                            "loop nest not optimized, code generation error\n");
 451         else
 452           dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
 453                            "loop nest optimized\n");
 454       }
 455
 456   if (dump_file && (dump_flags & TDF_DETAILS))
 457     {
 458       loop_p loop;
 459       int num_no_dependency = 0;
 460
 461       FOR_EACH_LOOP (loop, 0)
 462         if (loop->can_be_parallel)
 463           num_no_dependency++;
 464
 465       fprintf (dump_file, "%d loops carried no dependency.\n",
 466                num_no_dependency);
 467     }
 468
 469   free_scops (scops);
 470   graphite_finalize (need_cfg_cleanup_p);
 471   the_isl_ctx = NULL;
 472   isl_ctx_free (ctx);
 473 }
 474
 475 #else /* If isl is not available: #ifndef HAVE_isl.  */
 476
 477 static void
 478 graphite_transform_loops (void)
 479 {
 480   sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 481 }
 482
 483 #endif
 484
 485
 486 static unsigned int
 487 graphite_transforms (struct function *fun)
 488 {
 489   if (number_of_loops (fun) <= 1)
 490     return 0;
 491
 492   graphite_transform_loops ();
 493
 494   return 0;
 495 }
 496
 497 static bool
 498 gate_graphite_transforms (void)
 499 {
 500   /* Enable -fgraphite pass if any one of the graphite optimization flags
 501      is turned on.  */
 502   if (flag_graphite_identity
 503       || flag_loop_parallelize_all
 504       || flag_loop_nest_optimize)
 505     flag_graphite = 1;
 506
 507   return flag_graphite != 0;
 508 }
 509
 510 namespace {
 511
 512 const pass_data pass_data_graphite =
 513 {
 514   GIMPLE_PASS, /* type */
 515   "graphite0", /* name */
 516   OPTGROUP_LOOP, /* optinfo_flags */
 517   TV_GRAPHITE, /* tv_id */
 518   ( PROP_cfg | PROP_ssa ), /* properties_required */
 519   0, /* properties_provided */
 520   0, /* properties_destroyed */
 521   0, /* todo_flags_start */
 522   0, /* todo_flags_finish */
 523 };
 524
 525 class pass_graphite : public gimple_opt_pass
 526 {
 527 public:
 528   pass_graphite (gcc::context *ctxt)
 529     : gimple_opt_pass (pass_data_graphite, ctxt)
 530   {}
 531
 532   /* opt_pass methods: */
 533   virtual bool gate (function *) { return gate_graphite_transforms (); }
 534
 535 }; // class pass_graphite
 536
 537 } // anon namespace
 538
 539 gimple_opt_pass *
 540 make_pass_graphite (gcc::context *ctxt)
 541 {
 542   return new pass_graphite (ctxt);
 543 }
 544
 545 namespace {
 546
 547 const pass_data pass_data_graphite_transforms =
 548 {
 549   GIMPLE_PASS, /* type */
 550   "graphite", /* name */
 551   OPTGROUP_LOOP, /* optinfo_flags */
 552   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 553   ( PROP_cfg | PROP_ssa ), /* properties_required */
 554   0, /* properties_provided */
 555   0, /* properties_destroyed */
 556   0, /* todo_flags_start */
 557   0, /* todo_flags_finish */
 558 };
 559
 560 class pass_graphite_transforms : public gimple_opt_pass
 561 {
 562 public:
 563   pass_graphite_transforms (gcc::context *ctxt)
 564     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 565   {}
 566
 567   /* opt_pass methods: */
 568   virtual bool gate (function *) { return gate_graphite_transforms (); }
 569   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 570
 571 }; // class pass_graphite_transforms
 572
 573 } // anon namespace
 574
 575 gimple_opt_pass *
 576 make_pass_graphite_transforms (gcc::context *ctxt)
 577 {
 578   return new pass_graphite_transforms (ctxt);
 579 }
 580
 581