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