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 "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, "\nGlobal 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");
 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, "\nSCoP 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");
 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
 207   scop_p scop;
 208
 209   FOR_EACH_VEC_ELT (scops, i, scop)
 210     print_graphite_scop_statistics (file, scop);
 211
 212   /* Print the loop structure.  */
 213   print_loops (file, 2);
 214   print_loops (file, 3);
 215 }
 216
 217 /* Deletes all scops in SCOPS.  */
 218
 219 static void
 220 free_scops (vec<scop_p> scops)
 221 {
 222   int i;
 223   scop_p scop;
 224
 225   FOR_EACH_VEC_ELT (scops, i, scop)
 226     free_scop (scop);
 227
 228   scops.release ();
 229 }
 230
 231 /* Transforms LOOP to the canonical loop closed SSA form.  */
 232
 233 static void
 234 canonicalize_loop_closed_ssa (loop_p loop)
 235 {
 236   edge e = single_exit (loop);
 237   basic_block bb;
 238   gphi_iterator psi;
 239
 240   if (!e || (e->flags & EDGE_COMPLEX))
 241     return;
 242
 243   bb = e->dest;
 244
 245   /* Make the loop-close PHI node BB contain only PHIs and have a
 246      single predecessor.  */
 247   if (single_pred_p (bb))
 248     {
 249       e = split_block_after_labels (bb);
 250       bb = e->src;
 251     }
 252   else
 253     {
 254       basic_block close = split_edge (e);
 255       e = single_succ_edge (close);
 256       for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 257         {
 258           gphi *phi = psi.phi ();
 259           use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
 260           tree arg = USE_FROM_PTR (use_p);
 261
 262           /* Only add close phi nodes for SSA_NAMEs defined in LOOP.  */
 263           if (TREE_CODE (arg) != SSA_NAME
 264               || SSA_NAME_IS_DEFAULT_DEF (arg)
 265               || ! flow_bb_inside_loop_p (loop,
 266                                           gimple_bb (SSA_NAME_DEF_STMT (arg))))
 267             continue;
 268
 269           tree res = copy_ssa_name (arg);
 270           gphi *close_phi = create_phi_node (res, close);
 271           add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
 272                        UNKNOWN_LOCATION);
 273           SET_USE (use_p, res);
 274         }
 275       bb = close;
 276     }
 277
 278   /* Eliminate duplicates.  This relies on processing loops from
 279      innermost to outer.  */
 280   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 281     {
 282       gphi_iterator gsi = psi;
 283       gphi *phi = psi.phi ();
 284
 285       /* At this point, PHI should be a close phi in normal form.  */
 286       gcc_assert (gimple_phi_num_args (phi) == 1);
 287
 288       /* Iterate over the next phis and remove duplicates.  */
 289       gsi_next (&gsi);
 290       while (!gsi_end_p (gsi))
 291         if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0))
 292           {
 293             replace_uses_by (gimple_phi_result (gsi.phi ()),
 294                              gimple_phi_result (phi));
 295             remove_phi_node (&gsi, true);
 296           }
 297         else
 298           gsi_next (&gsi);
 299     }
 300 }
 301
 302 /* Converts the current loop closed SSA form to a canonical form
 303    expected by the Graphite code generation.
 304
 305    The loop closed SSA form has the following invariant: a variable
 306    defined in a loop that is used outside the loop appears only in the
 307    phi nodes in the destination of the loop exit.  These phi nodes are
 308    called close phi nodes.
 309
 310    The canonical loop closed SSA form contains the extra invariants:
 311
 312    - when the loop contains only one exit, the close phi nodes contain
 313    only one argument.  That implies that the basic block that contains
 314    the close phi nodes has only one predecessor, that is a basic block
 315    in the loop.
 316
 317    - the basic block containing the close phi nodes does not contain
 318    other statements.
 319
 320    - there exist only one phi node per definition in the loop.
 321 */
 322
 323 static void
 324 canonicalize_loop_closed_ssa_form (void)
 325 {
 326   loop_p loop;
 327   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 328     canonicalize_loop_closed_ssa (loop);
 329
 330   checking_verify_loop_closed_ssa (true);
 331 }
 332
 333 isl_ctx *the_isl_ctx;
 334
 335 /* Perform a set of linear transforms on the loops of the current
 336    function.  */
 337
 338 void
 339 graphite_transform_loops (void)
 340 {
 341   int i;
 342   scop_p scop;
 343   bool changed = false;
 344   vec<scop_p> scops = vNULL;
 345   isl_ctx *ctx;
 346
 347   /* If a function is parallel it was most probably already run through graphite
 348      once. No need to run again.  */
 349   if (parallelized_function_p (cfun->decl))
 350     return;
 351
 352   calculate_dominance_info (CDI_DOMINATORS);
 353
 354   ctx = isl_ctx_alloc ();
 355   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 356   the_isl_ctx = ctx;
 357
 358   sort_sibling_loops (cfun);
 359   canonicalize_loop_closed_ssa_form ();
 360
 361   calculate_dominance_info (CDI_POST_DOMINATORS);
 362   build_scops (&scops);
 363   free_dominance_info (CDI_POST_DOMINATORS);
 364
 365   if (dump_file && (dump_flags & TDF_DETAILS))
 366     {
 367       print_graphite_statistics (dump_file, scops);
 368       print_global_statistics (dump_file);
 369     }
 370
 371   FOR_EACH_VEC_ELT (scops, i, scop)
 372     if (dbg_cnt (graphite_scop))
 373       {
 374         scop->isl_context = ctx;
 375         if (!build_poly_scop (scop))
 376           continue;
 377
 378         if (!apply_poly_transforms (scop))
 379           continue;
 380
 381         changed = true;
 382         if (graphite_regenerate_ast_isl (scop))
 383           {
 384             location_t loc = find_loop_location
 385               (scops[i]->scop_info->region.entry->dest->loop_father);
 386             dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
 387                              "loop nest optimized\n");
 388           }
 389       }
 390
 391   if (changed)
 392     {
 393       mark_virtual_operands_for_renaming (cfun);
 394       update_ssa (TODO_update_ssa);
 395       checking_verify_ssa (true, true);
 396       rewrite_into_loop_closed_ssa (NULL, 0);
 397       scev_reset ();
 398       checking_verify_loop_structure ();
 399     }
 400
 401   if (dump_file && (dump_flags & TDF_DETAILS))
 402     {
 403       loop_p loop;
 404       int num_no_dependency = 0;
 405
 406       FOR_EACH_LOOP (loop, 0)
 407         if (loop->can_be_parallel)
 408           num_no_dependency++;
 409
 410       fprintf (dump_file, "%d loops carried no dependency.\n",
 411                num_no_dependency);
 412     }
 413
 414   free_scops (scops);
 415   the_isl_ctx = NULL;
 416   isl_ctx_free (ctx);
 417
 418   if (changed)
 419     {
 420       cleanup_tree_cfg ();
 421       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 422       release_recorded_exits (cfun);
 423       tree_estimate_probability (false);
 424     }
 425
 426 }
 427
 428 #else /* If isl is not available: #ifndef HAVE_isl.  */
 429
 430 static void
 431 graphite_transform_loops (void)
 432 {
 433   sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 434 }
 435
 436 #endif
 437
 438
 439 static unsigned int
 440 graphite_transforms (struct function *fun)
 441 {
 442   if (number_of_loops (fun) <= 1)
 443     return 0;
 444
 445   graphite_transform_loops ();
 446
 447   return 0;
 448 }
 449
 450 static bool
 451 gate_graphite_transforms (void)
 452 {
 453   /* Enable -fgraphite pass if any one of the graphite optimization flags
 454      is turned on.  */
 455   if (flag_graphite_identity
 456       || flag_loop_parallelize_all
 457       || flag_loop_nest_optimize)
 458     flag_graphite = 1;
 459
 460   return flag_graphite != 0;
 461 }
 462
 463 namespace {
 464
 465 const pass_data pass_data_graphite =
 466 {
 467   GIMPLE_PASS, /* type */
 468   "graphite0", /* name */
 469   OPTGROUP_LOOP, /* optinfo_flags */
 470   TV_GRAPHITE, /* tv_id */
 471   ( PROP_cfg | PROP_ssa ), /* properties_required */
 472   0, /* properties_provided */
 473   0, /* properties_destroyed */
 474   0, /* todo_flags_start */
 475   0, /* todo_flags_finish */
 476 };
 477
 478 class pass_graphite : public gimple_opt_pass
 479 {
 480 public:
 481   pass_graphite (gcc::context *ctxt)
 482     : gimple_opt_pass (pass_data_graphite, ctxt)
 483   {}
 484
 485   /* opt_pass methods: */
 486   virtual bool gate (function *) { return gate_graphite_transforms (); }
 487
 488 }; // class pass_graphite
 489
 490 } // anon namespace
 491
 492 gimple_opt_pass *
 493 make_pass_graphite (gcc::context *ctxt)
 494 {
 495   return new pass_graphite (ctxt);
 496 }
 497
 498 namespace {
 499
 500 const pass_data pass_data_graphite_transforms =
 501 {
 502   GIMPLE_PASS, /* type */
 503   "graphite", /* name */
 504   OPTGROUP_LOOP, /* optinfo_flags */
 505   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 506   ( PROP_cfg | PROP_ssa ), /* properties_required */
 507   0, /* properties_provided */
 508   0, /* properties_destroyed */
 509   0, /* todo_flags_start */
 510   0, /* todo_flags_finish */
 511 };
 512
 513 class pass_graphite_transforms : public gimple_opt_pass
 514 {
 515 public:
 516   pass_graphite_transforms (gcc::context *ctxt)
 517     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 518   {}
 519
 520   /* opt_pass methods: */
 521   virtual bool gate (function *) { return gate_graphite_transforms (); }
 522   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 523
 524 }; // class pass_graphite_transforms
 525
 526 } // anon namespace
 527
 528 gimple_opt_pass *
 529 make_pass_graphite_transforms (gcc::context *ctxt)
 530 {
 531   return new pass_graphite_transforms (ctxt);
 532 }
 533
 534