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