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 "fold-const.h"
  47 #include "gimple-iterator.h"
  48 #include "tree-cfg.h"
  49 #include "tree-ssa-loop.h"
  50 #include "tree-data-ref.h"
  51 #include "tree-scalar-evolution.h"
  52 #include "dbgcnt.h"
  53 #include "tree-parloops.h"
  54 #include "tree-cfgcleanup.h"
  55 #include "tree-vectorizer.h"
  56 #include "graphite.h"
  57
  58 /* Print global statistics to FILE.  */
  59
  60 static void
  61 print_global_statistics (FILE* file)
  62 {
  63   long n_bbs = 0;
  64   long n_loops = 0;
  65   long n_stmts = 0;
  66   long n_conditions = 0;
  67   profile_count n_p_bbs = profile_count::zero ();
  68   profile_count n_p_loops = profile_count::zero ();
  69   profile_count n_p_stmts = profile_count::zero ();
  70   profile_count n_p_conditions = profile_count::zero ();
  71
  72   basic_block bb;
  73
  74   FOR_ALL_BB_FN (bb, cfun)
  75     {
  76       gimple_stmt_iterator psi;
  77
  78       n_bbs++;
  79       if (bb->count.initialized_p ())
  80         n_p_bbs += bb->count;
  81
  82       /* Ignore artificial surrounding loop.  */
  83       if (bb == bb->loop_father->header
  84           && bb->index != 0)
  85         {
  86           n_loops++;
  87           n_p_loops += bb->count;
  88         }
  89
  90       if (EDGE_COUNT (bb->succs) > 1)
  91         {
  92           n_conditions++;
  93           if (bb->count.initialized_p ())
  94             n_p_conditions += bb->count;
  95         }
  96
  97       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
  98         {
  99           n_stmts++;
 100           if (bb->count.initialized_p ())
 101             n_p_stmts += bb->count;
 102         }
 103     }
 104
 105   fprintf (file, "\nGlobal statistics (");
 106   fprintf (file, "BBS:%ld, ", n_bbs);
 107   fprintf (file, "LOOPS:%ld, ", n_loops);
 108   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 109   fprintf (file, "STMTS:%ld)\n", n_stmts);
 110   fprintf (file, "\nGlobal profiling statistics (");
 111   fprintf (file, "BBS:");
 112   n_p_bbs.dump (file);
 113   fprintf (file, ", LOOPS:");
 114   n_p_loops.dump (file);
 115   fprintf (file, ", CONDITIONS:");
 116   n_p_conditions.dump (file);
 117   fprintf (file, ", STMTS:");
 118   n_p_stmts.dump (file);
 119   fprintf (file, ")\n");
 120 }
 121
 122 /* Print statistics for SCOP to FILE.  */
 123
 124 static void
 125 print_graphite_scop_statistics (FILE* file, scop_p scop)
 126 {
 127   long n_bbs = 0;
 128   long n_loops = 0;
 129   long n_stmts = 0;
 130   long n_conditions = 0;
 131   profile_count n_p_bbs = profile_count::zero ();
 132   profile_count n_p_loops = profile_count::zero ();
 133   profile_count n_p_stmts = profile_count::zero ();
 134   profile_count n_p_conditions = profile_count::zero ();
 135
 136   basic_block bb;
 137
 138   FOR_ALL_BB_FN (bb, cfun)
 139     {
 140       gimple_stmt_iterator psi;
 141       loop_p loop = bb->loop_father;
 142
 143       if (!bb_in_sese_p (bb, scop->scop_info->region))
 144         continue;
 145
 146       n_bbs++;
 147       if (bb->count.initialized_p ())
 148         n_p_bbs += bb->count;
 149
 150       if (EDGE_COUNT (bb->succs) > 1)
 151         {
 152           n_conditions++;
 153           n_p_conditions += bb->count;
 154         }
 155
 156       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 157         {
 158           n_stmts++;
 159           n_p_stmts += bb->count;
 160         }
 161
 162       if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
 163         {
 164           n_loops++;
 165           n_p_loops += bb->count;
 166         }
 167     }
 168
 169   fprintf (file, "\nFunction Name: %s\n", current_function_name ());
 170
 171   edge scop_begin = scop->scop_info->region.entry;
 172   edge scop_end = scop->scop_info->region.exit;
 173
 174   fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
 175            scop_begin->src->index, scop_begin->dest->index);
 176   fprintf (file, "exit_edge (bb_%d, bb_%d))",
 177            scop_end->src->index, scop_end->dest->index);
 178
 179   fprintf (file, "\nSCoP statistics (");
 180   fprintf (file, "BBS:%ld, ", n_bbs);
 181   fprintf (file, "LOOPS:%ld, ", n_loops);
 182   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 183   fprintf (file, "STMTS:%ld)\n", n_stmts);
 184   fprintf (file, "\nSCoP profiling statistics (");
 185   fprintf (file, "BBS:");
 186   n_p_bbs.dump (file);
 187   fprintf (file, ", LOOPS:");
 188   n_p_loops.dump (file);
 189   fprintf (file, ", CONDITIONS:");
 190   n_p_conditions.dump (file);
 191   fprintf (file, ", STMTS:");
 192   n_p_stmts.dump (file);
 193   fprintf (file, ")\n");
 194 }
 195
 196 /* Print statistics for SCOPS to FILE.  */
 197
 198 static void
 199 print_graphite_statistics (FILE* file, vec<scop_p> scops)
 200 {
 201   int i;
 202
 203   scop_p scop;
 204
 205   FOR_EACH_VEC_ELT (scops, i, scop)
 206     print_graphite_scop_statistics (file, scop);
 207
 208   /* Print the loop structure.  */
 209   print_loops (file, 2);
 210   print_loops (file, 3);
 211 }
 212
 213 /* Initialize graphite: when there are no loops returns false.  */
 214
 215 static bool
 216 graphite_initialize (isl_ctx *ctx)
 217 {
 218   int min_loops = PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION);
 219   int max_bbs = PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION);
 220   int nbbs = n_basic_blocks_for_fn (cfun);
 221   int nloops = number_of_loops (cfun);
 222
 223   if (nloops <= min_loops
 224       /* FIXME: This limit on the number of basic blocks of a function
 225          should be removed when the SCOP detection is faster.  */
 226       || (nbbs > max_bbs))
 227     {
 228       if (dump_file && (dump_flags & TDF_DETAILS))
 229         {
 230           if (nloops <= min_loops)
 231             fprintf (dump_file, "\nFunction does not have enough loops: "
 232                      "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n",
 233                      min_loops);
 234
 235           else if (nbbs > max_bbs)
 236             fprintf (dump_file, "\nFunction has too many basic blocks: "
 237                      "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs);
 238
 239           fprintf (dump_file, "\nnumber of SCoPs: 0\n");
 240           print_global_statistics (dump_file);
 241         }
 242
 243       isl_ctx_free (ctx);
 244       return false;
 245     }
 246
 247   scev_reset ();
 248   recompute_all_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   free_dominance_info (CDI_POST_DOMINATORS);
 267   if (need_cfg_cleanup_p)
 268     {
 269       free_dominance_info (CDI_DOMINATORS);
 270       scev_reset ();
 271       cleanup_tree_cfg ();
 272       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 273       release_recorded_exits (cfun);
 274       tree_estimate_probability (false);
 275     }
 276
 277   free_original_copy_tables ();
 278
 279   if (dump_file && dump_flags)
 280     print_loops (dump_file, 3);
 281 }
 282
 283 /* Deletes all scops in SCOPS.  */
 284
 285 static void
 286 free_scops (vec<scop_p> scops)
 287 {
 288   int i;
 289   scop_p scop;
 290
 291   FOR_EACH_VEC_ELT (scops, i, scop)
 292     free_scop (scop);
 293
 294   scops.release ();
 295 }
 296
 297 isl_ctx *the_isl_ctx;
 298
 299 /* Perform a set of linear transforms on the loops of the current
 300    function.  */
 301
 302 void
 303 graphite_transform_loops (void)
 304 {
 305   int i;
 306   scop_p scop;
 307   bool need_cfg_cleanup_p = false;
 308   vec<scop_p> scops = vNULL;
 309   isl_ctx *ctx;
 310
 311   /* If a function is parallel it was most probably already run through graphite
 312      once. No need to run again.  */
 313   if (parallelized_function_p (cfun->decl))
 314     return;
 315
 316   ctx = isl_ctx_alloc ();
 317   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 318   if (!graphite_initialize (ctx))
 319     return;
 320
 321   the_isl_ctx = ctx;
 322   build_scops (&scops);
 323
 324   if (dump_file && (dump_flags & TDF_DETAILS))
 325     {
 326       print_graphite_statistics (dump_file, scops);
 327       print_global_statistics (dump_file);
 328     }
 329
 330   FOR_EACH_VEC_ELT (scops, i, scop)
 331     if (dbg_cnt (graphite_scop))
 332       {
 333         scop->isl_context = ctx;
 334         if (!build_poly_scop (scop))
 335           continue;
 336
 337         if (!apply_poly_transforms (scop))
 338           continue;
 339
 340         need_cfg_cleanup_p = true;
 341         /* When code generation is not successful, do not continue
 342            generating code for the next scops: the IR has to be cleaned up
 343            and could be in an inconsistent state.  */
 344         if (!graphite_regenerate_ast_isl (scop))
 345           break;
 346
 347         location_t loc = find_loop_location
 348                            (scop->scop_info->region.entry->dest->loop_father);
 349         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
 350                          "loop nest optimized\n");
 351       }
 352
 353   free_scops (scops);
 354   graphite_finalize (need_cfg_cleanup_p);
 355   the_isl_ctx = NULL;
 356   isl_ctx_free (ctx);
 357 }
 358
 359 #else /* If isl is not available: #ifndef HAVE_isl.  */
 360
 361 static void
 362 graphite_transform_loops (void)
 363 {
 364   sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 365 }
 366
 367 #endif
 368
 369
 370 static unsigned int
 371 graphite_transforms (struct function *fun)
 372 {
 373   if (number_of_loops (fun) <= 1)
 374     return 0;
 375
 376   graphite_transform_loops ();
 377
 378   return 0;
 379 }
 380
 381 static bool
 382 gate_graphite_transforms (void)
 383 {
 384   /* Enable -fgraphite pass if any one of the graphite optimization flags
 385      is turned on.  */
 386   if (flag_graphite_identity
 387       || flag_loop_parallelize_all
 388       || flag_loop_nest_optimize)
 389     flag_graphite = 1;
 390
 391   return flag_graphite != 0;
 392 }
 393
 394 namespace {
 395
 396 const pass_data pass_data_graphite =
 397 {
 398   GIMPLE_PASS, /* type */
 399   "graphite0", /* name */
 400   OPTGROUP_LOOP, /* optinfo_flags */
 401   TV_GRAPHITE, /* tv_id */
 402   ( PROP_cfg | PROP_ssa ), /* properties_required */
 403   0, /* properties_provided */
 404   0, /* properties_destroyed */
 405   0, /* todo_flags_start */
 406   0, /* todo_flags_finish */
 407 };
 408
 409 class pass_graphite : public gimple_opt_pass
 410 {
 411 public:
 412   pass_graphite (gcc::context *ctxt)
 413     : gimple_opt_pass (pass_data_graphite, ctxt)
 414   {}
 415
 416   /* opt_pass methods: */
 417   virtual bool gate (function *) { return gate_graphite_transforms (); }
 418
 419 }; // class pass_graphite
 420
 421 } // anon namespace
 422
 423 gimple_opt_pass *
 424 make_pass_graphite (gcc::context *ctxt)
 425 {
 426   return new pass_graphite (ctxt);
 427 }
 428
 429 namespace {
 430
 431 const pass_data pass_data_graphite_transforms =
 432 {
 433   GIMPLE_PASS, /* type */
 434   "graphite", /* name */
 435   OPTGROUP_LOOP, /* optinfo_flags */
 436   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 437   ( PROP_cfg | PROP_ssa ), /* properties_required */
 438   0, /* properties_provided */
 439   0, /* properties_destroyed */
 440   0, /* todo_flags_start */
 441   0, /* todo_flags_finish */
 442 };
 443
 444 class pass_graphite_transforms : public gimple_opt_pass
 445 {
 446 public:
 447   pass_graphite_transforms (gcc::context *ctxt)
 448     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 449   {}
 450
 451   /* opt_pass methods: */
 452   virtual bool gate (function *) { return gate_graphite_transforms (); }
 453   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 454
 455 }; // class pass_graphite_transforms
 456
 457 } // anon namespace
 458
 459 gimple_opt_pass *
 460 make_pass_graphite_transforms (gcc::context *ctxt)
 461 {
 462   return new pass_graphite_transforms (ctxt);
 463 }
 464
 465