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