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