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               || SSA_NAME_IS_DEFAULT_DEF (arg)
 330               || ! flow_bb_inside_loop_p (loop,
 331                                           gimple_bb (SSA_NAME_DEF_STMT (arg))))
 332             continue;
 333
 334           tree res = copy_ssa_name (arg);
 335           gphi *close_phi = create_phi_node (res, close);
 336           add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
 337                        UNKNOWN_LOCATION);
 338           SET_USE (use_p, res);
 339         }
 340       bb = close;
 341     }
 342
 343   /* Eliminate duplicates.  This relies on processing loops from
 344      innermost to outer.  */
 345   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 346     {
 347       gphi_iterator gsi = psi;
 348       gphi *phi = psi.phi ();
 349
 350       /* At this point, PHI should be a close phi in normal form.  */
 351       gcc_assert (gimple_phi_num_args (phi) == 1);
 352
 353       /* Iterate over the next phis and remove duplicates.  */
 354       gsi_next (&gsi);
 355       while (!gsi_end_p (gsi))
 356         if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0))
 357           {
 358             replace_uses_by (gimple_phi_result (gsi.phi ()),
 359                              gimple_phi_result (phi));
 360             remove_phi_node (&gsi, true);
 361           }
 362         else
 363           gsi_next (&gsi);
 364     }
 365 }
 366
 367 /* Converts the current loop closed SSA form to a canonical form
 368    expected by the Graphite code generation.
 369
 370    The loop closed SSA form has the following invariant: a variable
 371    defined in a loop that is used outside the loop appears only in the
 372    phi nodes in the destination of the loop exit.  These phi nodes are
 373    called close phi nodes.
 374
 375    The canonical loop closed SSA form contains the extra invariants:
 376
 377    - when the loop contains only one exit, the close phi nodes contain
 378    only one argument.  That implies that the basic block that contains
 379    the close phi nodes has only one predecessor, that is a basic block
 380    in the loop.
 381
 382    - the basic block containing the close phi nodes does not contain
 383    other statements.
 384
 385    - there exist only one phi node per definition in the loop.
 386 */
 387
 388 static void
 389 canonicalize_loop_closed_ssa_form (void)
 390 {
 391   loop_p loop;
 392   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 393     canonicalize_loop_closed_ssa (loop);
 394
 395   checking_verify_loop_closed_ssa (true);
 396 }
 397
 398 isl_ctx *the_isl_ctx;
 399
 400 /* Perform a set of linear transforms on the loops of the current
 401    function.  */
 402
 403 void
 404 graphite_transform_loops (void)
 405 {
 406   int i;
 407   scop_p scop;
 408   bool need_cfg_cleanup_p = false;
 409   vec<scop_p> scops = vNULL;
 410   isl_ctx *ctx;
 411
 412   /* If a function is parallel it was most probably already run through graphite
 413      once. No need to run again.  */
 414   if (parallelized_function_p (cfun->decl))
 415     return;
 416
 417   if (!graphite_initialize ())
 418     return;
 419
 420   ctx = isl_ctx_alloc ();
 421   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 422   the_isl_ctx = ctx;
 423
 424   sort_sibling_loops (cfun);
 425   canonicalize_loop_closed_ssa_form ();
 426
 427   calculate_dominance_info (CDI_POST_DOMINATORS);
 428   build_scops (&scops);
 429   free_dominance_info (CDI_POST_DOMINATORS);
 430
 431   if (dump_file && (dump_flags & TDF_DETAILS))
 432     {
 433       print_graphite_statistics (dump_file, scops);
 434       print_global_statistics (dump_file);
 435     }
 436
 437   FOR_EACH_VEC_ELT (scops, i, scop)
 438     if (dbg_cnt (graphite_scop))
 439       {
 440         scop->isl_context = ctx;
 441         if (!build_poly_scop (scop))
 442           continue;
 443
 444         if (!apply_poly_transforms (scop))
 445           continue;
 446
 447         location_t loc = find_loop_location
 448           (scops[i]->scop_info->region.entry->dest->loop_father);
 449
 450         need_cfg_cleanup_p = true;
 451         if (!graphite_regenerate_ast_isl (scop))
 452           dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
 453                            "loop nest not optimized, code generation error\n");
 454         else
 455           dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
 456                            "loop nest optimized\n");
 457       }
 458
 459   if (dump_file && (dump_flags & TDF_DETAILS))
 460     {
 461       loop_p loop;
 462       int num_no_dependency = 0;
 463
 464       FOR_EACH_LOOP (loop, 0)
 465         if (loop->can_be_parallel)
 466           num_no_dependency++;
 467
 468       fprintf (dump_file, "%d loops carried no dependency.\n",
 469                num_no_dependency);
 470     }
 471
 472   free_scops (scops);
 473   graphite_finalize (need_cfg_cleanup_p);
 474   the_isl_ctx = NULL;
 475   isl_ctx_free (ctx);
 476 }
 477
 478 #else /* If isl is not available: #ifndef HAVE_isl.  */
 479
 480 static void
 481 graphite_transform_loops (void)
 482 {
 483   sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 484 }
 485
 486 #endif
 487
 488
 489 static unsigned int
 490 graphite_transforms (struct function *fun)
 491 {
 492   if (number_of_loops (fun) <= 1)
 493     return 0;
 494
 495   graphite_transform_loops ();
 496
 497   return 0;
 498 }
 499
 500 static bool
 501 gate_graphite_transforms (void)
 502 {
 503   /* Enable -fgraphite pass if any one of the graphite optimization flags
 504      is turned on.  */
 505   if (flag_graphite_identity
 506       || flag_loop_parallelize_all
 507       || flag_loop_nest_optimize)
 508     flag_graphite = 1;
 509
 510   return flag_graphite != 0;
 511 }
 512
 513 namespace {
 514
 515 const pass_data pass_data_graphite =
 516 {
 517   GIMPLE_PASS, /* type */
 518   "graphite0", /* name */
 519   OPTGROUP_LOOP, /* optinfo_flags */
 520   TV_GRAPHITE, /* tv_id */
 521   ( PROP_cfg | PROP_ssa ), /* properties_required */
 522   0, /* properties_provided */
 523   0, /* properties_destroyed */
 524   0, /* todo_flags_start */
 525   0, /* todo_flags_finish */
 526 };
 527
 528 class pass_graphite : public gimple_opt_pass
 529 {
 530 public:
 531   pass_graphite (gcc::context *ctxt)
 532     : gimple_opt_pass (pass_data_graphite, ctxt)
 533   {}
 534
 535   /* opt_pass methods: */
 536   virtual bool gate (function *) { return gate_graphite_transforms (); }
 537
 538 }; // class pass_graphite
 539
 540 } // anon namespace
 541
 542 gimple_opt_pass *
 543 make_pass_graphite (gcc::context *ctxt)
 544 {
 545   return new pass_graphite (ctxt);
 546 }
 547
 548 namespace {
 549
 550 const pass_data pass_data_graphite_transforms =
 551 {
 552   GIMPLE_PASS, /* type */
 553   "graphite", /* name */
 554   OPTGROUP_LOOP, /* optinfo_flags */
 555   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 556   ( PROP_cfg | PROP_ssa ), /* properties_required */
 557   0, /* properties_provided */
 558   0, /* properties_destroyed */
 559   0, /* todo_flags_start */
 560   0, /* todo_flags_finish */
 561 };
 562
 563 class pass_graphite_transforms : public gimple_opt_pass
 564 {
 565 public:
 566   pass_graphite_transforms (gcc::context *ctxt)
 567     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 568   {}
 569
 570   /* opt_pass methods: */
 571   virtual bool gate (function *) { return gate_graphite_transforms (); }
 572   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 573
 574 }; // class pass_graphite_transforms
 575
 576 } // anon namespace
 577
 578 gimple_opt_pass *
 579 make_pass_graphite_transforms (gcc::context *ctxt)
 580 {
 581   return new pass_graphite_transforms (ctxt);
 582 }
 583
 584