gcc/graphite.c

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