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 #include "config.h"
  31
  32 #ifdef HAVE_isl
  33 /* Workaround for GMP 5.1.3 bug, see PR56019.  */
  34 #include <stddef.h>
  35
  36 #include <isl/constraint.h>
  37 #include <isl/set.h>
  38 #include <isl/map.h>
  39 #include <isl/options.h>
  40 #include <isl/union_map.h>
  41 #endif
  42
  43 #include "system.h"
  44 #include "coretypes.h"
  45 #include "backend.h"
  46 #include "diagnostic-core.h"
  47 #include "cfgloop.h"
  48 #include "tree-pass.h"
  49 #include "params.h"
  50
  51 #ifdef HAVE_isl
  52 #include "cfghooks.h"
  53 #include "tree.h"
  54 #include "gimple.h"
  55 #include "fold-const.h"
  56 #include "gimple-iterator.h"
  57 #include "tree-cfg.h"
  58 #include "tree-ssa-loop.h"
  59 #include "tree-data-ref.h"
  60 #include "tree-scalar-evolution.h"
  61 #include "graphite-poly.h"
  62 #include "dbgcnt.h"
  63 #include "tree-parloops.h"
  64 #include "tree-cfgcleanup.h"
  65 #include "graphite-scop-detection.h"
  66 #include "graphite-isl-ast-to-gimple.h"
  67 #include "graphite-sese-to-poly.h"
  68
  69 /* Print global statistics to FILE.  */
  70
  71 static void
  72 print_global_statistics (FILE* file)
  73 {
  74   long n_bbs = 0;
  75   long n_loops = 0;
  76   long n_stmts = 0;
  77   long n_conditions = 0;
  78   long n_p_bbs = 0;
  79   long n_p_loops = 0;
  80   long n_p_stmts = 0;
  81   long n_p_conditions = 0;
  82
  83   basic_block bb;
  84
  85   FOR_ALL_BB_FN (bb, cfun)
  86     {
  87       gimple_stmt_iterator psi;
  88
  89       n_bbs++;
  90       n_p_bbs += bb->count;
  91
  92       /* Ignore artificial surrounding loop.  */
  93       if (bb == bb->loop_father->header
  94           && bb->index != 0)
  95         {
  96           n_loops++;
  97           n_p_loops += bb->count;
  98         }
  99
 100       if (EDGE_COUNT (bb->succs) > 1)
 101         {
 102           n_conditions++;
 103           n_p_conditions += bb->count;
 104         }
 105
 106       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 107         {
 108           n_stmts++;
 109           n_p_stmts += bb->count;
 110         }
 111     }
 112
 113   fprintf (file, "\nGlobal statistics (");
 114   fprintf (file, "BBS:%ld, ", n_bbs);
 115   fprintf (file, "LOOPS:%ld, ", n_loops);
 116   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 117   fprintf (file, "STMTS:%ld)\n", n_stmts);
 118   fprintf (file, "\nGlobal profiling statistics (");
 119   fprintf (file, "BBS:%ld, ", n_p_bbs);
 120   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 121   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 122   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 123 }
 124
 125 /* Print statistics for SCOP to FILE.  */
 126
 127 static void
 128 print_graphite_scop_statistics (FILE* file, scop_p scop)
 129 {
 130   long n_bbs = 0;
 131   long n_loops = 0;
 132   long n_stmts = 0;
 133   long n_conditions = 0;
 134   long n_p_bbs = 0;
 135   long n_p_loops = 0;
 136   long n_p_stmts = 0;
 137   long n_p_conditions = 0;
 138
 139   basic_block bb;
 140
 141   FOR_ALL_BB_FN (bb, cfun)
 142     {
 143       gimple_stmt_iterator psi;
 144       loop_p loop = bb->loop_father;
 145
 146       if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 147         continue;
 148
 149       n_bbs++;
 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_REGION (scop)))
 165         {
 166           n_loops++;
 167           n_p_loops += bb->count;
 168         }
 169     }
 170
 171   fprintf (file, "\nSCoP statistics (");
 172   fprintf (file, "BBS:%ld, ", n_bbs);
 173   fprintf (file, "LOOPS:%ld, ", n_loops);
 174   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 175   fprintf (file, "STMTS:%ld)\n", n_stmts);
 176   fprintf (file, "\nSCoP profiling statistics (");
 177   fprintf (file, "BBS:%ld, ", n_p_bbs);
 178   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 179   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 180   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 181 }
 182
 183 /* Print statistics for SCOPS to FILE.  */
 184
 185 static void
 186 print_graphite_statistics (FILE* file, vec<scop_p> scops)
 187 {
 188   int i;
 189
 190   scop_p scop;
 191
 192   FOR_EACH_VEC_ELT (scops, i, scop)
 193     print_graphite_scop_statistics (file, scop);
 194 }
 195
 196 /* Initialize graphite: when there are no loops returns false.  */
 197
 198 static bool
 199 graphite_initialize (isl_ctx *ctx)
 200 {
 201   if (number_of_loops (cfun) <= 1
 202       /* FIXME: This limit on the number of basic blocks of a function
 203          should be removed when the SCOP detection is faster.  */
 204       || (n_basic_blocks_for_fn (cfun) >
 205           PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)))
 206     {
 207       if (dump_file && (dump_flags & TDF_DETAILS))
 208         print_global_statistics (dump_file);
 209
 210       isl_ctx_free (ctx);
 211       return false;
 212     }
 213
 214   scev_reset ();
 215   recompute_all_dominators ();
 216   initialize_original_copy_tables ();
 217
 218   if (dump_file && dump_flags)
 219     dump_function_to_file (current_function_decl, dump_file, dump_flags);
 220
 221   return true;
 222 }
 223
 224 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
 225    true.  */
 226
 227 static void
 228 graphite_finalize (bool need_cfg_cleanup_p)
 229 {
 230   if (need_cfg_cleanup_p)
 231     {
 232       scev_reset ();
 233       cleanup_tree_cfg ();
 234       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 235       release_recorded_exits ();
 236       tree_estimate_probability ();
 237     }
 238
 239   free_original_copy_tables ();
 240
 241   if (dump_file && dump_flags)
 242     print_loops (dump_file, 3);
 243 }
 244
 245 isl_ctx *the_isl_ctx;
 246
 247 /* Perform a set of linear transforms on the loops of the current
 248    function.  */
 249
 250 void
 251 graphite_transform_loops (void)
 252 {
 253   int i;
 254   scop_p scop;
 255   bool need_cfg_cleanup_p = false;
 256   vec<scop_p> scops = vNULL;
 257   isl_ctx *ctx;
 258
 259   /* If a function is parallel it was most probably already run through graphite
 260      once. No need to run again.  */
 261   if (parallelized_function_p (cfun->decl))
 262     return;
 263
 264   ctx = isl_ctx_alloc ();
 265   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 266   if (!graphite_initialize (ctx))
 267     return;
 268
 269   the_isl_ctx = ctx;
 270   build_scops (&scops);
 271
 272   if (dump_file && (dump_flags & TDF_DETAILS))
 273     {
 274       print_graphite_statistics (dump_file, scops);
 275       print_global_statistics (dump_file);
 276     }
 277
 278   FOR_EACH_VEC_ELT (scops, i, scop)
 279     if (dbg_cnt (graphite_scop))
 280       {
 281         scop->ctx = ctx;
 282         build_poly_scop (scop);
 283
 284         if (dump_file && dump_flags)
 285           print_scop (dump_file, scop, 3);
 286
 287         if (POLY_SCOP_P (scop)
 288             && apply_poly_transforms (scop)
 289             && graphite_regenerate_ast_isl (scop))
 290           need_cfg_cleanup_p = true;
 291
 292       }
 293
 294   free_scops (scops);
 295   graphite_finalize (need_cfg_cleanup_p);
 296   the_isl_ctx = NULL;
 297   isl_ctx_free (ctx);
 298 }
 299
 300 #else /* If ISL is not available: #ifndef HAVE_isl.  */
 301
 302 static void
 303 graphite_transform_loops (void)
 304 {
 305   sorry ("Graphite loop optimizations cannot be used (ISL is not available).");
 306 }
 307
 308 #endif
 309
 310
 311 static unsigned int
 312 graphite_transforms (struct function *fun)
 313 {
 314   if (number_of_loops (fun) <= 1)
 315     return 0;
 316
 317   graphite_transform_loops ();
 318
 319   return 0;
 320 }
 321
 322 static bool
 323 gate_graphite_transforms (void)
 324 {
 325   /* Enable -fgraphite pass if any one of the graphite optimization flags
 326      is turned on.  */
 327   if (flag_graphite_identity
 328       || flag_loop_parallelize_all
 329       || flag_loop_optimize_isl)
 330     flag_graphite = 1;
 331
 332   return flag_graphite != 0;
 333 }
 334
 335 namespace {
 336
 337 const pass_data pass_data_graphite =
 338 {
 339   GIMPLE_PASS, /* type */
 340   "graphite0", /* name */
 341   OPTGROUP_LOOP, /* optinfo_flags */
 342   TV_GRAPHITE, /* tv_id */
 343   ( PROP_cfg | PROP_ssa ), /* properties_required */
 344   0, /* properties_provided */
 345   0, /* properties_destroyed */
 346   0, /* todo_flags_start */
 347   0, /* todo_flags_finish */
 348 };
 349
 350 class pass_graphite : public gimple_opt_pass
 351 {
 352 public:
 353   pass_graphite (gcc::context *ctxt)
 354     : gimple_opt_pass (pass_data_graphite, ctxt)
 355   {}
 356
 357   /* opt_pass methods: */
 358   virtual bool gate (function *) { return gate_graphite_transforms (); }
 359
 360 }; // class pass_graphite
 361
 362 } // anon namespace
 363
 364 gimple_opt_pass *
 365 make_pass_graphite (gcc::context *ctxt)
 366 {
 367   return new pass_graphite (ctxt);
 368 }
 369
 370 namespace {
 371
 372 const pass_data pass_data_graphite_transforms =
 373 {
 374   GIMPLE_PASS, /* type */
 375   "graphite", /* name */
 376   OPTGROUP_LOOP, /* optinfo_flags */
 377   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 378   ( PROP_cfg | PROP_ssa ), /* properties_required */
 379   0, /* properties_provided */
 380   0, /* properties_destroyed */
 381   0, /* todo_flags_start */
 382   0, /* todo_flags_finish */
 383 };
 384
 385 class pass_graphite_transforms : public gimple_opt_pass
 386 {
 387 public:
 388   pass_graphite_transforms (gcc::context *ctxt)
 389     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 390   {}
 391
 392   /* opt_pass methods: */
 393   virtual bool gate (function *) { return gate_graphite_transforms (); }
 394   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 395
 396 }; // class pass_graphite_transforms
 397
 398 } // anon namespace
 399
 400 gimple_opt_pass *
 401 make_pass_graphite_transforms (gcc::context *ctxt)
 402 {
 403   return new pass_graphite_transforms (ctxt);
 404 }
 405
 406