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