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