gcc/graphite.c

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