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