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